Determinare per quali valori di $ p $ primo , $ \displaystyle \frac {2^{p-1} -1}{p} $ è un quadrao perfetto.
Da uno stage di Parma di qualche anno fa.
Quando è un quadrato perfetto?
Quando è un quadrato perfetto?
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.
Re: Quando è un quadrato perfetto?
Rilancio:
(b) Quando $\displaystyle \frac {11^{p-1} -1}{p}$ è un quadrato perfetto?
(c) Quando $\displaystyle \frac {7^{p-1} -1}{p}$ è un quadrato perfetto?
Queste due sono notevolmente più complicate (ha qualcosa a che fare con il fatto che 11 e 7 non sono pari
) e provengono da un esercizio del WC2010 (mi pare N5, ma non sono sicuro)
(b) Quando $\displaystyle \frac {11^{p-1} -1}{p}$ è un quadrato perfetto?
(c) Quando $\displaystyle \frac {7^{p-1} -1}{p}$ è un quadrato perfetto?
Queste due sono notevolmente più complicate (ha qualcosa a che fare con il fatto che 11 e 7 non sono pari
) e provengono da un esercizio del WC2010 (mi pare N5, ma non sono sicuro)Re: Quando è un quadrato perfetto?
Dai, provo temerariamente a rispondere al quesito base:
si deve avere che $2^{p-1}-1 = px^2$. Siccome $2 \mid p-1$, si ha che $2^{p-1}-1 \equiv 0 \mod{3}$ e che quindi $3 |px^2$ e $p \equiv 3 \mod{4}$. Scrivo quindi $p=4k-1$.
Bon, si ha quindi che $3|2^{4k-2}-1 = (2^{2k-1}-1)(2^{2k-1}+1) = px^2$. Si ha quindi che siccome $3 \not \mid 2^{2k-1}-1$, che $3|2^{2k-1}+1$. Usando il lifting lemma, si ha ora quindi che $v_3(2^{2k-1}+1) = v_3(3)+v_3(2k+1)$: siccome si deve avere che l'esponente di ogni fattore primo di quel prodotto sia pari, allora abbiamo che $v_3(2^{2k-1}+1) = v_3(3)+v_3(2k+1)= 1+v_3(2k+1) \in 2\mathbb{Z}+1$ e quindi $2k+1 = 3^{2j+1}h$ ($(h,3)=1$) da cui deriva che $k = \frac{3^{2j+1}h-1}{2}$. Si deve avere ora che $-h-1 \equiv 0 \mod{2}$ e quindi $(2,h)=1$. Scrivo $h=2z+1$ e, svolti i vari passaggi, si Ottiene che $p=2\cdot 3^{2j+1}(2z+1)+1$. Tornando al punto di partenza si deve però avere che $2^{2\cdot3^{2j+1}(2z+1)}-1 = x^2\cdot (2\cdot 3^{2j+1}(2z+1)+1)$. Ora, si vede subito che $2^{2\cdot3^{2j+1}(2z+1)} \equiv 0 \mod{8}$ sempre. si ha quindi che $1 \equiv x^2\cdot 2 \cdot (2z+1) +x^2$: essendo i residui quadratici modulo 8 $\{ 0,1,4 \}$ si vede facendo qualche conto che nessuno di questi residui è accettabile per risolvere l'equazione sopra, e quindi l'equazione di partenza non ha soluzione.
si deve avere che $2^{p-1}-1 = px^2$. Siccome $2 \mid p-1$, si ha che $2^{p-1}-1 \equiv 0 \mod{3}$ e che quindi $3 |px^2$ e $p \equiv 3 \mod{4}$. Scrivo quindi $p=4k-1$.
Bon, si ha quindi che $3|2^{4k-2}-1 = (2^{2k-1}-1)(2^{2k-1}+1) = px^2$. Si ha quindi che siccome $3 \not \mid 2^{2k-1}-1$, che $3|2^{2k-1}+1$. Usando il lifting lemma, si ha ora quindi che $v_3(2^{2k-1}+1) = v_3(3)+v_3(2k+1)$: siccome si deve avere che l'esponente di ogni fattore primo di quel prodotto sia pari, allora abbiamo che $v_3(2^{2k-1}+1) = v_3(3)+v_3(2k+1)= 1+v_3(2k+1) \in 2\mathbb{Z}+1$ e quindi $2k+1 = 3^{2j+1}h$ ($(h,3)=1$) da cui deriva che $k = \frac{3^{2j+1}h-1}{2}$. Si deve avere ora che $-h-1 \equiv 0 \mod{2}$ e quindi $(2,h)=1$. Scrivo $h=2z+1$ e, svolti i vari passaggi, si Ottiene che $p=2\cdot 3^{2j+1}(2z+1)+1$. Tornando al punto di partenza si deve però avere che $2^{2\cdot3^{2j+1}(2z+1)}-1 = x^2\cdot (2\cdot 3^{2j+1}(2z+1)+1)$. Ora, si vede subito che $2^{2\cdot3^{2j+1}(2z+1)} \equiv 0 \mod{8}$ sempre. si ha quindi che $1 \equiv x^2\cdot 2 \cdot (2z+1) +x^2$: essendo i residui quadratici modulo 8 $\{ 0,1,4 \}$ si vede facendo qualche conto che nessuno di questi residui è accettabile per risolvere l'equazione sopra, e quindi l'equazione di partenza non ha soluzione.
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Quando è un quadrato perfetto?
p=3 
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.
Re: Quando è un quadrato perfetto?
Lol, ok allora se $j=0$ si ha infatti $p=3$ ed è l'unico caso in cui "Ora, si vede subito che $2^{2⋅3^{2j+1}(2z+1)}≡0mod8 sempre." è falso. Bon, mi sa che è quella l'unica soluzioneamatrix92 ha scritto:p=3
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Quando è un quadrato perfetto?
p=7
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.
Re: Quando è un quadrato perfetto?
Mist ha scritto:Scrivo quindi $p=4k-1$
Mist ha scritto:...da cui deriva che $k = \frac{3^{2j+1}h-1}{2}$.
Forse all'inizio volevi scrivere $p=4k+3$? Anche perché qui utilizzi il lifting the exponents come se l'esponente fosse $2k+1=\dfrac{(4k+3)-1}{2}$Mist ha scritto:...svolti i vari passaggi, si Ottiene che $p=2\cdot 3^{2j+1}(2z+1)+1$...
A parte questo typo, se analizzo $2^{2\cdot3^{2j+1}(2z+1)}-1 = x^2\cdot (2\cdot 3^{2j+1}(2z+1)+1)$ modulo 8 (escludendo il caso patologico), ottengo $-1 \equiv x^2\cdot (2\cdot 3\cdot(2z+1)+1) \equiv x^2(12z+7) \equiv x^2(4z-1)$. Ma se $x^2\equiv 1 \pmod 8$, ti viene $4z\equiv 0 \pmod 8$. E questo vale se $z$ è pari.Mist ha scritto: $v_3(2^{2k-1}+1) = v_3(3)+v_3(2k+1)= 1+v_3(2k+1)$
Per una soluzione diversa metto un hint nascosto
Testo nascosto:
Trovare tutte le coppie $(a,p)$ con $a \in \mathbb{N}$ e $p$ primo tali che $\dfrac{a^{p-1}-1}{p}$ è un quadrato.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Quando è un quadrato perfetto?
Oggi nell'ora di inglese ho buttato giù questo, dovrebbe reggere.
Allora il caso p=2 non va, quindi posto p diverso da 2 essendo p coprimo con 2 possiamo applicare il piccolo teorema di fermat in forma $2^{p-1} \equiv 1 \pmod p$ da cui segue $2^{p-1}-1 \equiv 0 \pmod p$ e quindi la frazione è sempre intera(fatto interessante ^^).
Poniamo adesso $p=2p_1+1 \Rightarrow \frac{2^{2p_1}-1}p\Rightarrow\frac{(2^{p_1}+1)(2^{p_1}-1)}p$ Adesso i due fattori sono dispari e differiscono di 2 quindi non hanno alcun fattore in comune, quindi p divide uno solo di essi, inoltre per essere quadrato perfetto il fattore che non è diviso da p deve essere un quadrato perfetto:
$2^{p_1}-1$ per $p_1=1\Rightarrow p=3 \Rightarrow \frac{2^{2}-1}3=1$ che è soluzione; per $p_1>2 \Rightarrow 2^{p_1}-1\equiv 3 \pmod 4$ che non è mai quadrato perfetto, quindi resta:
$2^{p_1}+1=k^2\Rightarrow 2^{p_1}=(k+1)(k-1)$ da cui essendo 4 e 2 le uniche potenze di due che differiscono di 2(posso darlo per scontato?) abbiamo $p_1=3\Rightarrow p=7$
Le uniche soluzioni sono quindi 3 e 7.
Allora il caso p=2 non va, quindi posto p diverso da 2 essendo p coprimo con 2 possiamo applicare il piccolo teorema di fermat in forma $2^{p-1} \equiv 1 \pmod p$ da cui segue $2^{p-1}-1 \equiv 0 \pmod p$ e quindi la frazione è sempre intera(fatto interessante ^^).
Poniamo adesso $p=2p_1+1 \Rightarrow \frac{2^{2p_1}-1}p\Rightarrow\frac{(2^{p_1}+1)(2^{p_1}-1)}p$ Adesso i due fattori sono dispari e differiscono di 2 quindi non hanno alcun fattore in comune, quindi p divide uno solo di essi, inoltre per essere quadrato perfetto il fattore che non è diviso da p deve essere un quadrato perfetto:
$2^{p_1}-1$ per $p_1=1\Rightarrow p=3 \Rightarrow \frac{2^{2}-1}3=1$ che è soluzione; per $p_1>2 \Rightarrow 2^{p_1}-1\equiv 3 \pmod 4$ che non è mai quadrato perfetto, quindi resta:
$2^{p_1}+1=k^2\Rightarrow 2^{p_1}=(k+1)(k-1)$ da cui essendo 4 e 2 le uniche potenze di due che differiscono di 2(posso darlo per scontato?) abbiamo $p_1=3\Rightarrow p=7$
Le uniche soluzioni sono quindi 3 e 7.
Ultima modifica di Claudio. il 03 feb 2011, 14:34, modificato 4 volte in totale.
Re: Quando è un quadrato perfetto?
Sono abbastanza convinto che il caso generico sia molto difficile, se non impossibile.. già il caso a=7 fa patire e non poco..bĕlcōlŏn ha scritto:Non so quanto difficile possa essere, ma propongo di ragionare anche su quest'a generalizzazione:
Trovare tutte le coppie $(a,p)$ con $a \in \mathbb{N}$ e $p$ primo tali che $\dfrac{a^{p-1}-1}{p}$ è un quadrato.
@Claudio: sì, direi giusto
ora prova con 11 xDRe: Quando è un quadrato perfetto?
Posto la soluzione per l'11 che, alla luce della soluzione di Claudio, è più facile ora.
1) Verifico il caso $ p=2 $, da cui non ottengo soluzione.
2) Poichè $ 2|p-1 $ posso allora scrivere $ \frac{11^{p-1}-1}{p}=\frac{(11^{\frac{p-1}{2}}+1)(11^{\frac{p-1}{2}}-1)}{p} $
3) Per lo stesso ragionamento fatto da claudio, poichè i fattori differiscono di due, possono al più contenere come fattor comune $ 2 $, ma siccome avevo posto $ p>2 $, ne consegue che $ p|(11^{\frac{p-1}{2}}-1) $ o $ p|(11^{\frac{p-1}{2}}+1) $ (or esclusivo)
3)a) se $ p|(11^{\frac{p-1}{2}}-1) $ $ \Rightarrow $ $ 11^{\frac{p-1}{2}}=n^2-1 $ e quindi $ 11^{\frac{p-1}{2}}=(n+1)(n-1) $. Siccome due potenze di undici non differiscono mai tra di loro per, al più, 2, allora non ci sono soluzioni.
3)b) se $ p|(11^{\frac{p-1}{2}}+1) $ $ \Rightarrow $ $ 11^{\frac{p-1}{2}}=n^2+1 $. Analizzando le congruenze $ mod11 $ verifico che i residui quadratici $ mod11 $ sono $ (0,1,3,4,5,-2) $, da cui verifico che non ci sono soluzioni.
Non ci sono dunque soluzioni. (e credo valga anche per il caso p=7, non vedo dove siano i problemi, non dovrebbe esserci un residuo quadratico di -1 nel 7 ; o magari ho sbagliato qualche passaggio io nella mia soluzione 
)
P.S. per il caso generale con a, il passo 3)a) della mia soluzione sarebbe facile da verificare, ma i residui quadratici $ moda $ nel passo 3b non saprei proprio come farli xd.
1) Verifico il caso $ p=2 $, da cui non ottengo soluzione.
2) Poichè $ 2|p-1 $ posso allora scrivere $ \frac{11^{p-1}-1}{p}=\frac{(11^{\frac{p-1}{2}}+1)(11^{\frac{p-1}{2}}-1)}{p} $
3) Per lo stesso ragionamento fatto da claudio, poichè i fattori differiscono di due, possono al più contenere come fattor comune $ 2 $, ma siccome avevo posto $ p>2 $, ne consegue che $ p|(11^{\frac{p-1}{2}}-1) $ o $ p|(11^{\frac{p-1}{2}}+1) $ (or esclusivo)
3)a) se $ p|(11^{\frac{p-1}{2}}-1) $ $ \Rightarrow $ $ 11^{\frac{p-1}{2}}=n^2-1 $ e quindi $ 11^{\frac{p-1}{2}}=(n+1)(n-1) $. Siccome due potenze di undici non differiscono mai tra di loro per, al più, 2, allora non ci sono soluzioni.
3)b) se $ p|(11^{\frac{p-1}{2}}+1) $ $ \Rightarrow $ $ 11^{\frac{p-1}{2}}=n^2+1 $. Analizzando le congruenze $ mod11 $ verifico che i residui quadratici $ mod11 $ sono $ (0,1,3,4,5,-2) $, da cui verifico che non ci sono soluzioni.
Non ci sono dunque soluzioni. (e credo valga anche per il caso p=7, non vedo dove siano i problemi, non dovrebbe esserci un residuo quadratico di -1 nel 7
; o magari ho sbagliato qualche passaggio io nella mia soluzione )P.S. per il caso generale con a, il passo 3)a) della mia soluzione sarebbe facile da verificare, ma i residui quadratici $ moda $ nel passo 3b non saprei proprio come farli xd.
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]
Re: Quando è un quadrato perfetto?
E chi ti dice che non ci siano un po' di fattori 2 in $11^{\frac{p-1}2}-1$ e un po' in $11^{\frac{p-1}2}+1$?
Re: Quando è un quadrato perfetto?
Lo sapevo io che c'era l'errore, e dire che ci ho pensato su un bel po' su quel punto per poi dire che era tutto a posto XD. Adesso vedo se riesco ad aggiustarla.[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]
Re: Quando è un quadrato perfetto?
Mi sono ricordato di questo problema Qualcuno lo risolva, io non riesco a concludere per $p_1$ pari....(parlo di quello con l'11).
Qualcuno lo risolva, io non riesco a concludere per $p_1$ pari....(parlo di quello con l'11).