Restos de 2^x: [tex3]2^1 \equiv2, \; 2^2 \equiv 4, \; 2^3 \equiv 1,[/tex3]
depois disso cicla.
Restos de x^2: [tex3]1^2 \equiv 1, \; 2^2 \equiv 4, \; 3^2 \equiv 2, \; 4^2 \equiv 2, \; 5^2 \equiv 4, \; 6^2 \equiv 1, \; 7^2 \equiv 0,[/tex3]
depos disso cicla (já que 8 é congruente a 1, 9 é congruente a 2, ...).
Os restos de [tex3]2^x[/tex3]
são representados na sequência de período 3 (2, 4, 1, 2, 4, 1, 2, 4, 1, ...) (Sequência A)
Os restos de [tex3]x^2[/tex3]
são representados na sequência de período 7 (1, 4, 2, 2, 4, 1, 0, 1, 4, 2, 2, 4, 1, 0, 1, 4, 2, 2, 4, 1, 0, ...) (Sequência B)
Então, encaixando os restos de [tex3]2^x[/tex3]
e [tex3]x^2[/tex3]
para cada valor de [tex3]x,[/tex3]
formamos a sequência de tuplas, na forma (resto de x^2, resto de 2^x):
[tex3](1,2),(4,4),(2,1),(2,2),...[/tex3]
(Sequência C)
Vamos encontrar o período dessa sequência. Para isso, vamos encontrar o menor valor de [tex3]n>1[/tex3]
para o qual a n-ésima tupla da sequência C é igual a (1,2), em que esse algarismo 1 veio obrigatoriamente de uma posição da forma [tex3]7q+1[/tex3]
da sequência B, [tex3]q[/tex3]
inteiro.
Ou seja, queremos o menor inteiro [tex3]n>1[/tex3]
tal que [tex3]n=7q+1[/tex3]
e [tex3]n=3m+1 \Longrightarrow 7q=3m[/tex3]
, com "q" e "m" inteiros.
Claramente devemos ter [tex3]m=7, \; q=3[/tex3]
e [tex3]n=22.[/tex3]
Ou seja, a sequência C tem período 21.
Vamos contar quantas vezes o resto de [tex3]2^x-x^2[/tex3]
é zero em um período. Ou seja, quantas vezes em um período os dois elementos das tuplas da sequência C são iguais.
Off Topic
Um jeito fácil de contar isso é pegar uma folha de papel na horizontal e escrever os 21 primeiros termos da sequência A, e depois acima ou abaixo escrever, nas mesmas posições horizontais, os elementos da sequência B. Isso é bem mais rápido do que escrever (1,2), (4,4), (2,1), ... porque escrevendo uma sequência de cada vez você rapidamente decora o padrão.
Observamos que, a cada período, o resto de [tex3]2^x-x^2[/tex3]
por 7 é zero 6 vezes.
Ou seja, de 1 a 21 contamos 6, de 22 a 42 contamos mais 6, de 43 a 63 contamos mais 6, assim por diante.
Temos [tex3] \left\lfloor \frac{10000}{21} \right\rfloor=476.[/tex3]
Assim, há 476 intervalos de tamanho [tex3]21[/tex3]
de 1 a 10000.
[tex3]476 \times 21=9996.[/tex3]
Então, de [tex3]x=1[/tex3]
a [tex3]x=9996,[/tex3]
há [tex3]476 \times 6=2856[/tex3]
ocorrências em que o resto é zero.
De [tex3]x=9997[/tex3]
a [tex3]x=10000,[/tex3]
basta escrever os 4 primeiros elementos de um período da sequência C:
(1,2), (4,4), (2,1), (2,2). Ou seja, o resto é zero duas vezes.
No total há [tex3]2856+2=2858[/tex3]
valores de [tex3]x[/tex3]
para o qual o resto é zero.
[tex3]10000-2858=\boxed{7142}[/tex3]