Classico TdN

[Jack2331]

Sia n un numero naturale dispari maggiore di 1. Provare che $n$ non divide $3^n+1$

[Mistral2]

Se $3$ divide $n$ si avrebbe $1 (mod 3)=0 (mod 3)$ chiaramente impossibile.
Se $3$ non divide $n$ risulta $MCD(3,n)=1$. Quindi per il teorema di eulero abbiamo anche che $3^{varphi(n)}=1 (mod n)$ quindi se fosse anche $3^n=-1 (mod n)$ sommando membro a membro, escludendo il caso $n=2$, si avrebbe che $3$ divide $n$ da cui di nuovo un assurdo.



Saluti

Mistral

[Jack2331]

Se $3$ non divide $n$ risulta $MCD(3,n)=1$. Quindi per il teorema di eulero abbiamo anche che $3^{varphi(n)}=1 (mod n)$ quindi se fosse anche $3^n=-1 (mod n)$ sommando membro a membro, escludendo il caso $n=2$, si avrebbe che $3$ divide $n$ da cui di nuovo un assurdo.

Direi che non va, in quanto sommando membro a membro, otterresti $3^n+3^{varphi(n)} = 0 (mod n)$, da cui $3^{varphi(n)}(3^{n-varphi(n)}+1) = 0 (mod n)$, e qui potrebbe essere anche $3^{n-varphi(n)}+1 = 0 (mod n)$...

[Mistral2]

"Jack233":

Se $3$ non divide $n$ risulta $MCD(3,n)=1$. Quindi per il teorema di eulero abbiamo anche che $3^{varphi(n)}=1 (mod n)$ quindi se fosse anche $3^n=-1 (mod n)$ sommando membro a membro, escludendo il caso $n=2$, si avrebbe che $3$ divide $n$ da cui di nuovo un assurdo.

Direi che non va, in quanto sommando membro a membro, otterresti $3^n+3^{varphi(n)} = 0 (mod n)$, da cui $3^{varphi(n)}(3^{n-varphi(n)}+1) = 0 (mod n)$, e qui potrebbe essere anche $3^{n-varphi(n)}+1 = 0 (mod n)$...

Si vero mi sono sbagliato, comunque, cerco di metterci una pezza.


Saluti

Mistral

[Mistral2]

"Mistral":[quote="Jack233"]

Se $3$ non divide $n$ risulta $MCD(3,n)=1$. Quindi per il teorema di eulero abbiamo anche che $3^{varphi(n)}=1 (mod n)$ quindi se fosse anche $3^n=-1 (mod n)$ sommando membro a membro, escludendo il caso $n=2$, si avrebbe che $3$ divide $n$ da cui di nuovo un assurdo.

Direi che non va, in quanto sommando membro a membro, otterresti $3^n+3^{varphi(n)} = 0 (mod n)$, da cui $3^{varphi(n)}(3^{n-varphi(n)}+1) = 0 (mod n)$, e qui potrebbe essere anche $3^{n-varphi(n)}+1 = 0 (mod n)$...

Si vero mi sono sbagliato, comunque, cerco di metterci una pezza.


Saluti

Mistral[/quote]

Se $3^{n-varphi(n)}+1 = 0 (mod n)$, con un procedimento analogo posso arrivare al fatto che il resto $r_1$ della divisione di $n$ con $varphi(n)$ deve soddisfare $3^{r_1}+1= (mod n)$. Sommando membro a membro con $3^{varphi(n)}=1 (mod n)$ ottengo $3^{varphi(n)-r_1} +1= 0 (mod n)$. Se $r_2$ é il resto della divisione di $varphi(n)$ per $r_1$ ottengo iterando il procedimento $3^{r_2}+1= (mod n)$. Sottraendo membro a membro con $3^{r_1}+1= (mod n)$ ottengo per $r_2$ la condizione $3^{r_1-r_2}-1=0 (mod n)$. Questo procedimento é quello dell'algoritmo di Euclide per il calcolo di $d=MCD(n,varphi(n))$ che come sappiamo termina con un resto nullo e il penultimo resto é $r_j=d$. Quindi si giunge a $3^{d}2= 0 (mod n)$ oppure $3^{r_{j-1}}2= 0 (mod n)$ da cui l'assurdo.

Lo corretta due o tre volte forse ora funziona dategli un occhiata. Comunque mi sembra un po' farraginosa.

Saluti

Mistral

[Jack2331]

"Mistral":

Se $3^{n-varphi(n)}+1 = 0 (mod n)$, con un procedimento analogo posso arrivare al fatto che il resto $r_1$ della divisione di $n$ con $varphi(n)$ deve soddisfare $3^{r_1}+1= (mod n)$. Sommando membro a membro con $3^{varphi(n)}=1 (mod n)$ ottengo $3^{varphi(n)-r_1} +1= 0 (mod n)$. Se $r_2$ é il resto della divisione di $varphi(n)$ per $r_1$ ottengo iterando il procedimento $3^{r_2}+1= (mod n)$. Sottraendo membro a membro con $3^{r_1}+1= (mod n)$ ottengo per $r_2$ la condizione $3^{r_1-r_2}-1=0 (mod n)$. Questo procedimento é quello dell'algoritmo di Euclide per il calcolo di $d=MCD(n,varphi(n))$ che come sappiamo termina con un resto nullo e il penultimo resto é $r_j=d$. Quindi si giunge a $3^{d}2= 0 (mod n)$ oppure $3^{r_{j-1}}2= 0 (mod n)$ da cui l'assurdo.

In effetti qualcosa che non va c'è....infatti la condizione come tu stesso hai scritto diventa $3^{r_1-r_2}-1=0 (modn)$. A questo punto arriveresti a $3^{r_3}-1=0(modn)$ . Osserva che c'è -1 e non +1 come invece in $r_1$ e in $r_2$, quindi crolla la tua tesi in quanto si potrebbe arrivare a $3^d=0 (modn)$ , che non è un assurdo.

Inoltre dovresti considerare il fatto che il penultimo resto (ossia l'MCD) può essere anche uno tra $r_1,r_2,r_3$, e quindi non si avrebbe l'assurdo in quanto avresti $3^d+1=0 (modn)$ oppure nel caso di $r_3$ avresti $3^d-1=0 (modn)$...

Ciao

Jack

[Mistral2]

"Jack233":[quote="Mistral"]

.... Questo procedimento é quello dell'algoritmo di Euclide per il calcolo di $d=MCD(n,varphi(n))$ che come sappiamo termina con un resto nullo e il penultimo resto é $r_j=d$. Quindi si giunge a $3^{d}2= 0 (mod n)$ oppure $3^{r_{j-1}}2= 0 (mod n)$ da cui l'assurdo.

In effetti qualcosa che non va c'è....infatti la condizione come tu stesso hai scritto diventa $3^{r_1-r_2}-1=0 (modn)$. A questo punto arriveresti a $3^{r_3}-1=0(modn)$ . Osserva che c'è -1 e non +1 come invece in $r_1$ e in $r_2$, quindi crolla la tua tesi in quanto si potrebbe arrivare a $3^d=0 (modn)$ , che non è un assurdo.

Inoltre dovresti considerare il fatto che il penultimo resto (ossia l'MCD) può essere anche uno tra $r_1,r_2,r_3$, e quindi non si avrebbe l'assurdo in quanto avresti $3^d+1=0 (modn)$ oppure nel caso di $r_3$ avresti $3^d-1=0 (modn)$...

[/quote]

Forse sono stato poco esplicito nello scrivere tutti passaggi. Comunque ho considerato la successione $r_k$ decrescente dei resti dell'algoritmo di Euclide applicato a $n$ e $varphi(n)$ con $r_{j}=d=MCD(n,varphi(n))$ quindi $r_{j+1}=0$. I segni alterni non mi sembravano un problema , infatti ho messo le due condizioni forse la seconda $3^{r_{j-1}}2= 0 (mod n)$ non funziona. Comunque appena ho tempo controllo meglio e la formalizzo più nel dettaglio, magari dagli un occhiata anche tu.

Ciao

Mistral

[Mistral2]

"Mistral":.........Comunque appena ho tempo controllo meglio e la formalizzo più nel dettaglio, magari dagli un occhiata anche tu.

Ciao

Mistral

Consideriamo la successione $r_k$ decrescente dei resti dell'algoritmo di Euclide applicato a $n$ e $varphi(n)$ con
$r_{j}=d=MCD(n,varphi(n))$ quindi $r_{j+1}=0$. Inoltre $r_{k-1}=q_{k}r_{k}+r_{k+1}$.

Possiamo avere tre casi

CASO 1

Eq(k-1,0) $3^{r_{k-1}}= 1 (mod n)$

Eq(k,0) $3^{r_{k}}= -1 (mod n)$


sommando membro a membro ed eliminado il fattore $3^{r_{k}}$ otteniamo

Eq(k-1,1) $3^{r_{k-1}-r_{k}}+1= 0 (mod n)$

che sostituiamo a Eq(k-1,0), possiamo di nuovo sommare membro a membro con Eq(k,0) ottenendo

Eq(k-1,2) $3^{r_{k-1}-2r_{k}}+1= 0 (mod n)$

.....

alla fine giungo a

Eq(k-1,q_{k})=Eq(k+1,0) $3^{r_{k+1}}+1= 0 (mod n)$

che sostituisco alla Eq(k-1,0)



CASO 2

Eq(k,0) $3^{r_{k}}= 1 (mod n)$

Eq(k+1,0) $3^{r_{k+1}}= -1 (mod n)$

sommando membro a membro ed eliminado il fattore $3^{r_{k+1}}$ otteniamo

Eq(k,1) $3^{r_{k}-r_{k+1}}+1= 0 (mod n)$

che sostituiamo a Eq(k,0), possiamo di nuovo sommare membro a membro con Eq(k+1,0) ottenendo

Eq(k,2) $3^{r_{k}-2r_{k+1}}+1= 0 (mod n)$

.....

alla fine giungo a

Eq(k,q_{k+1})=Eq(k+2,0) $3^{r_{k+2}}+1= 0 (mod n)$

che sostituisco alla Eq(k,0)


CASO 3

Eq(k+1,0) $3^{r_{k+1}}= -1 (mod n)$

Eq(k+2,0) $3^{r_{k+2}}= -1 (mod n)$

sottraggo membro a membro ed eliminado il fattore $3^{r_{k+2}}$ otteniamo

Eq(k+1,1) $3^{r_{k+1}-r_{k+2}}-1= 0 (mod n)$

che sostituiamo a Eq(k+1,0), possiamo di nuovo sommare membro a membro con Eq(k+2,0) ottenendo

Eq(k+1,1) $3^{r_{k+1}-2r_{k+2}}-1= 0 (mod n)$

.....

alla fine giungo a

Eq(k+1,q_{k+2})=Eq(k+3,0) $3^{r_{k+3}}-1= 0 (mod n)$

che sostituisco alla Eq(k+1,0).

Dopo si ritorna ciclicamente al CASO 1, abbiamo quindi tre possibilità:

(1) Se $j=k $ abbiamo l'assurdo $2=0 (mod n)$.
(2) Se $j=k+1$ abbiamo l'assurdo $2=0 (mod n)$.
(3) Se $j=k+2$ abbiamo l'assurdo $3^{r_{k+2}}= -1 (mod n)$ e $3^{r_{k+2}}= 1 (mod n)$

Ora mi sembra giusto, anche se non la definirei una soluzione classica.

Saluti


Mistral

[Jack2331]

Un paio di cose:

Nel (3) dici di ottenere l'assurdo con $3^{r_{k+2}} = 1 (mod n)$ e $3^{r_{k+2}}= -1 (mod n)$. Questo non è un assurdo in quanto i tre casi che descrivi prima non si verificano contemporaneamente, quindi si avrà solo un'equazione tra le due che dici, e quindi non hai l'assurdo.

Inoltre si potrebbe avere anche che $j$ sia diverso da $k,k+1,k+2$, per esempio sia $k+3$ o $k+i$ in genere. Che succede in questo caso?

[Mistral2]

"Jack233":Un paio di cose:

Nel (3) dici di ottenere l'assurdo con $3^{r_{k+2}} = 1 (mod n)$ e $3^{r_{k+2}}= -1 (mod n)$. Questo non è un assurdo in quanto i tre casi che descrivi prima non si verificano contemporaneamente, quindi si avrà solo un'equazione tra le due che dici, e quindi non hai l'assurdo.

Inoltre si potrebbe avere anche che $j$ sia diverso da $k,k+1,k+2$, per esempio sia $k+3$ o $k+i$ in genere. Che succede in questo caso?

I tre casi esauriscono le possibilitá, e in tutti tre i casi si giunge ad un assurdo. Se vedi bene si verificano contemporaneamente tutte e due le equazioni in quanto, se $r_{k+3}=0$, allora $r_{k+1}=q_{k+2}r_{k+2}$ quindi sottraendo $q_{k+2}-1$ volte il numero $r_{k+2}$ ottengo l'equazione con $+1$. Non é necessario che i tre casi si presentino contemporaneamente, per altro é anche sbagliato concettualmente. Se parti da $k=1$ con $r_1=varphi(n)$ e $r_{-1}=n$ e vai di tre in tre ottieni tutti i casi possibili fino a giungere al resto nullo, quindi $k$ indica il ciclo di $3$ passi generico. Ho esaminato per $k$ generico l'accadimento del resto nullo in ciascuno dei passi, ottenendo sempre l'assurdo. Questa volta non ti ho capito. Forse dovevo fare il riassunto delle puntate precedenti ad ogni risposta, quando trovo il tempo ti scrivo tutta la dimostrazione per esteso cosí ti risulta piú chiara giusta o sbagliata che sia .

Ciao

Mistral

[bboypa]

Sia $p \in \mathfrak{P}$ il piu piccolo primo tale che $p|n$. Allora $3^{p \frac{n}{p}} \equiv 3^{\frac{n}{p}} \equiv -1 \mod p \implies 2\frac{n}{p} | \varphi(p)=p-1$ chiaramente assurdo per la minimalità di $p$.