Olimpíadas

Mensagem não lidapor **majik** » Dom 13 Abr, 2014 14:21 · Mensagem não lida por **majik** » Dom 13 Abr, 2014 14:21

Encontre todos os primos [tex3]p[/tex3] , para os quais o quociente.

[tex3]\frac{2^{p-1}-1}{p}[/tex3]
é um quadrado perfeito.

Cara, não consegui resolver ainda mas vou deixar aqui algumas observações que eu acho que podem ajudar a resolver esse problema:

Se $p=2$ teremos:

$\frac{2^{1}-1}{2} =\frac{1}{2}$
então $p=2$ não nos convém.

Pelo pequeno teorema de fermat se $mdc(a,p)=1$ e $p$ é primo então:

$a^{p-1}\equiv1\, mod(p)$

Se $p\neq 2$ então o pequeno teorema de fermat garante que
$2^{p-1} -1$ é múltiplo de $p$

o problema pede que:
$2^{p-1} -1=p\cdot n^{2}$

como $p$ é ímpar podemos dizer que $2^{p-1}$ é um quadrado perfeito. Pois o expoente é par. Mais do que isso $2^{p-1}$ não é divisível por 3. Pois é uma potência de 2.

Lema: Todo quadrado perfeito $m^2$ quando dividido por 3 deixa restos:
1 - se $m$ não for múltiplo de 3
0 - se $m$ é múltiplo de 3

Prova: ou $m = 3k$ pra $k$ inteiro positivo então $m^2=9k^2=3\cdot(3k^2)$
ou $m = 3k+1$ então $m^2 = 9k^2+6k+1=3(3k^2+2k)+1$
ou $m=3k+2$ então $m^2=9k^2+12k+4=9k^2+12k+3+1=3(3k^2+4k+1)+1$
cqd

então temos que $2^{p-1} \equiv 1\, mod(3) \rightarrow 2^{p-1} - 1 \equiv 0\, mod(3)$ então devemos ter que:
$p \cdot n^2 \equiv 0\, mod(3)$
excetuando-se o caso $p=3$ que satisfaz a condição do problema pois:
$\frac{2^{2}-1}{3}=1$
devemos ter então $n=3k$ e é fácil ver que $n$ deve ser ímpar, pois $2^{p-1}-1$ é ímpar e $p$ também é. Então $n=3(2m-1)$ .
Com esta descoberta podemos inferir agora que se $p>3$ então $2^{p-1}-1 \equiv 0 \, mod(9)$
observemos que:
$2^0 \equiv 1\,mod(9)$
$2^1 \equiv 2\,mod(9)$
$2^2 \equiv 4\,mod(9)$
$2^3 \equiv 8\,mod(9)$
$2^4 \equiv 2\cdot8\,mod(9)\equiv 16\, mod(9) \equiv 7\, mod(9)$
$2^5 \equiv 2\cdot7 \,mod(9)\equiv 5 \, mod(9)$
$2^6 \equiv 2\cdot5\,mod(9)\equiv 10\,mod(9) \equiv 1\,mod(9)$
e a partir dai o padrão se repete.
Então $2^{n}-1$ só é divisível por 9 se $n=6k$ pra algum $k$ inteiro não-negativo, então temos que $p-1=6k \rightarrow p=6k+1 (*)$

teremos:
$2^{p-1}-1=p \cdot 9\, \cdot (2m-1)^2$

Lema: todo quadrado perfeito ímpar deixa resto 1 quando dividido por 4. Todo quadrado perfeito par é divisível por 4.
Prova: Seja $m=2k-1$ então $m^2=4k^2-4k+1=4k(k-1)+1$

pra os primos $p$ com $p>3$ temos que $2^{p-1}$ é divisível por 4 então:
$2^{p-1} -1 \equiv 3 \, mod(4)$
do lado direito:
$9\, \cdot p \cdot (2m-1)^2 \equiv p\,mod(4)$
então
$p \equiv 3 \, mod(4) \rightarrow p =4x +3(**)$

$(*)$ e $(**)$ : $6k+1=4x+3 \rightarrow 3k=2x+1\rightarrow x=\frac{3k-1}{2} = k-1+\frac{k+1}{2}$
$k+1=2y \rightarrow k =2y-1 \rightarrow x = 3y-2$
vou só mostrar que $x$ deve ser ímpar e deixar indicada a PA em que $p$ se encontra. Pelo teorema de Dirichlet para progressões aritméticas, temos que existem infinitos primos nessa sequência, então eu não resolvi o problema, mas o restringi um pouco. Espero que isso sirva pra alguém.

Lema: todo quadrado perfeito ímpar deixa resto 1 quando dividido por 8.
Prova: Seja $m=2k-1$ então $m^2=4k^2-4k+1=4k(k-1)+1$
é fácil ver que $k(k-1)$ é par.
pra os primos $p$ com $p>3$ temos que $2^{p-1}$ é divisível por 8 então:
$2^{p-1} -1 \equiv 7 \, mod(8)$
do lado direito:
$9\, \cdot p \cdot (2m-1)^2 \equiv p\,mod(8)$
então
$p \equiv 7 \, mod(8) \rightarrow p =8z +7 = 4x + 3\rightarrow x=2z+1$ cqd
como
$x=3y-2$ então $y=2i-1$
$p=4(3(2i-1)-2)+3 =4(6i-5)+3=24i-17$
alguns candidatos a solução são: $7,31,79,103,127,...$

$2^{p-1} = 2^{24i-18} = 2^{24k+6} = 2^{6(4k+1)}$
$2^6 \equiv 8\cdot8\mod(7)\equiv1 \mod(7)$
$2^{24} \equiv (2^6)^4\mod(7) \equiv 1 \mod(7)$

logo para todo primo da forma $24i-17$ $2^{p-1} - 1 \equiv 0\mod(7)$
excetuando-se o caso $p=7$ isso implica que $n = 9 \cdot 49 \cdot (2m-1)^2$

$2^{24i-18}$ só vai ser $1 \mod(49)$ quando $i = 6 + 7k$
$p-1 = 24(6+7k) - 18 = 168k + 126$
$p = 168k + 127$

Mensagem não lidapor **Vinisth** » Sex 09 Jan, 2015 11:58

Ol,á a todos,

Primeiro faz-se o teste com $p=2$ , como sousóeu fez.
Todo primo $p>2$ é ímpar, logo seja p da foma $p=2n+1 \ ,\ n \in N \implies 2^{2n}-1=(2^n-1)(2^n+1)=(2n+1)x^2$
Como $mdc(2^n-1, 2^n+1)=1$ e cada fator é um número ímpar consecutivo, a equação se torna em resolver :
$\begin{cases} 2^n-1=py^2 \\ 2^n+1=t^2 \end{cases} \ \ \ ou \ \ \ \begin{cases} 2^n-1=t^2 \\ 2^n+1=py^2 \end{cases}$

$2^n=t^2-1=(t-1)(t+1)$
Ambos fatores devem ser potências de 2, isso só acontece
$\iff t-1=2^u \, \ , t+1=2^v \implies 2^v-2^u=2 \implies v=2\ , u=1$
Logo, só tem solução para $t=3 \implies n=3 \implies p=7$ , analogamente pode-se ter $p=3$ .

Os números são $\{3,7\}$
Para complemento: Fermat Quotient

Abraço !

Olimpíadas ⇒ Números primos

Números primos

Re: Números primos

Re: Números primos

Re: Números primos

Olimpíadas ⇒ Números primos

Números primos

Re: Números primos

Re: Números primos

Re: Números primos

Entrar • Registrar