TdN for dummies

[alvinlee88]

Dato che Levacci si fa attendere (anche se credo che il secondo caso sia analogo al primo..) posto un problemino piuttosto semplice per ingannare l'attesa
Trovare il Massimo Comun Divisore di tutti i numeri della forma $n^73-n$, con $n inNN$. Buon divertimento!

[Gabriel]

L'ultimo problema della serie è rimasto irrisolto - che peccato. Gli rispondo, così, proponendone una generalizzazione.

Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.

[Iacopo]

Mi pare evidente che (a-2)! sia congruo a 0 (mod a) per ogni a composto.
Infatti ogni fattore di a è necessariamente <= a/2 e quindi <= (a-2). Ne segue che è contenuto in (a-2)!
O sbaglio?

[Gabriel]

Mi pare evidente che (a-2)! sia congruo a 0 (mod a) per ogni a composto.
Infatti ogni fattore di a è necessariamente <= a/2 e quindi <= (a-2). Ne segue che è contenuto in (a-2)!
O sbaglio?

... eppure $4$ non divide $2!$. Quindi il tuo ragionamento, da qualche parte, deve pur fallire. Inoltre non è chiaro - almeno a me - a quale problema tu stia rispondendo.

[Iacopo]

Infatti ho scritto una cavolata, rispondendo a un problema posto un po' di tempo fate. Scusate.

[alvinlee88]

L'ultimo problema della serie è rimasto irrisolto - che peccato. Gli rispondo, così, proponendone una generalizzazione.

Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.

Vorrei rispondere con la limitazione $ninNN$, la generalizzazione a $ZZ$ ci penso domani.. Per i casi $n=0,1$ si vede bene che esistono infiniti divisori del nostro $t=n^p-n$. Osserviamo che, se $n$ è pari, $t$ è pari, mentre se $n$ è dispari, $t$ è comunque pari. Quindi $2$ è un divisore.
Vediamo poi che $p$ è un divisore, in quanto per il piccolo teorema di Fermat $n^p=n(modp)$.
Fuori da questi casi particolari, si ha che $AAq$ primo $n^p-n=0(modq)<=>n^(p-1)=1(modq)$, perchè il caso $n=0(mod q)$ è stato escluso, visto che non crea problemi. Sappiamo che per $q$ primo $n^(q-1)=1(mod q)$ (sempre a condizione che $(n,q)=1$)e quindi vale anche $n^(k*(q-1))=(n^(q-1))^k=1(mod q)$.
Quindi se $EE kinZZ$ tale che $(q-1)*k=p-1$, cioè se $q-1|p-1$ abbiamo che $n^(p-1)=1(modq)$, cioè $q$ è un divisore di $t$. Detto $q(i)$ l'i-esimo primo ($q(1)=2$ $q(2)=3$ ...) definiamo $A={q(i) | i in NN, q(i)-1|p-1}$. Allora l'MCD dell'insieme ${n^p - n}$ è il prodotto di tutti gli elementi di $A$.
Che ne dite, è giusta? Quando ho postato il caso con $p=73$ non ero del tutto sicuro della soluzione, ho postato anche per avere conferme o smentite. Alla fine poi mi sono risposto da solo. Spero qualcosa di buono ci sia in quello che ho scritto.. caio

[Gabriel]

Vorrei rispondere con la limitazione $ninNN$, la generalizzazione a $ZZ$ ci penso domani.. Per i casi $n=0,1$ si vede bene che esistono infiniti divisori del nostro $t=n^p-n$. Osserviamo che, se $n$ è pari, $t$ è pari, mentre se $n$ è dispari, $t$ è comunque pari. Quindi $2$ è un divisore.
Vediamo poi che $p$ è un divisore, in quanto per il piccolo teorema di Fermat $n^p=n(modp)$.
Fuori da questi casi particolari, si ha che $AAq$ primo $n^p-n=0(modq)<=>n^(p-1)=1(modq)$, perchè il caso $n=0(mod q)$ è stato escluso, visto che non crea problemi. Sappiamo che per $q$ primo $n^(q-1)=1(mod q)$ (sempre a condizione che $(n,q)=1$)e quindi vale anche $n^(k*(q-1))=(n^(q-1))^k=1(mod q)$.
Quindi se $EE kinZZ$ tale che $(q-1)*k=p-1$, cioè se $q-1|p-1$ abbiamo che $n^(p-1)=1(modq)$, cioè $q$ è un divisore di $t$. Detto $q(i)$ l'i-esimo primo ($q(1)=2$ $q(2)=3$ ...) definiamo $A={q(i) | i in NN, q(i)-1|p-1}$. Allora l'MCD dell'insieme ${n^p - n}$ è il prodotto di tutti gli elementi di $A$. [...] Spero qualcosa di buono ci sia in quello che ho scritto.

Di buono c'è tanto, ma andrebbe un attimino risistemato ... In sintesi, tu affermi che, qualunque sia $p \in NN$, purché primo, il massimo comun divisore $m_p$ dell'insieme $\{n^p-n\}_{n \in ZZ}$ è divisibile per $p$ e per qualunque altro primo $q \in NN$ tale che $(q-1) | (p-1)$. Questo, tuttavia, non dice nulla di definitivo sulla fattorizzazione di $m_p$, visto che - in linea di principio - non stabilisce quale sia il massimo esponente $\alpha \in NN$ con cui un generico primo $q \in NN$ possa dividere $m_p$ né esclude la possibilità che esistano divisori primi di $m_p$, diversi da quelli già elencati. In ogni caso, è di per sé già un buon inizio.

[alvinlee88]

Giustissimo, sono andato di fretta. Vedo di rimediare. Dimostro che non ne esistono altri oltre a quelli che ho detto io (dopo dimostrerò che gli esponenti dei $qinA$ devono essere per forza $1$), cioè voglio dimostrare che, per $q$ primo, $q|n^p-n =>qinA$, ovverosia "$q$ non appartiene ad $A$"$ =>$"$q$ non divide $n^p-n$".
Se $q$ non appartiene a $A$, allora, per definizione di $A$, $q-1$ non divide $p-1$, cioè $p-1=(q-1)k+h$, con $k,h in ZZ$, con $h!=0(mod q-1)$ (perchè altrimenti avremmo che $(q-1)|p-1$). Poichè $n^p-n\equiv0(modq)<=>n^(p-1)\equiv1(modq)$ (sempre con le condizioni dell'altro post), dimostriamo che $n^(p-1)!=1(modq)$, con l'ipotesi $p-1=(q-1)k+h$, con $k,h in ZZ$, con $h!=0(mod q-1)$. Se per assurdo fosse $n^(p-1)\equiv1(modq)$, si avrebbe $n^(k*(q-1))*n^h\equiv1(modq)$, cioè $n^h\equiv1(modq)$ , in quanto $n^(k*(q-1))\equiv1(modq))$ (poichè $n^(q-1)\equiv1(modq)$ per Fermat, con la solita condizione su n e q), ma $n^h\equiv1(modq)$ se e solo se $h$ è un multiplo dell'ordine di $n$ in $q$, che è $q-1$. Ma $h!=0(mod q-1)$ per ipotesi. Assurdo. Quindi i possibili divisori sono tutti e soli gli elementi di $A$, e dunque il massimo primo che divide $n^p-n$ è proprio $p$. Dimostriamo ora che non possono esserci esponenti maggiori di $1$ per gli elementi di $A$
$m_p$ deve per definizione dividere ogni elemento del'insieme $B={n^p-n}_(n inNN)$, quindi in particolare deve dividere $q^p-q=q(q^(p-1)-1)$, con $q in A$ . Sia$a inNN$. Si vede che per ogni $a>1$, $q^a$ non divide $q^p-q$, perchè se $a<=p$ allora $q^(a-1)$ deve dividere $q^(p-1) -1$, e questo è impossibile poichè $q^(a-1)|q^(p-1)$, mentre se $a>=p+1$ dovrebbe essere che $q^(p+j)$, con $j>=0$, divide $q^(p-1)-1$ chiaramente impossibile. Quindi nessun esponente dei $qinA$ può essere maggiore di $1$.
In conclusione, $m_p$ è proprio il prodotto di tutti gli elementi di $A$.
Che ne pensi?

[Gabriel]

[...] ma $n^h\equiv1(modq)$ se e solo se $h$ è un multiplo dell'ordine di $n$ in $q$, che è $q-1$. [...]

Tutto a posto, con la sola eccezione della proposizione quotata qui sopra, dal momento che l'ordine moltiplicativo di $q$ alla base $n$ non è necessariamente $q-1$, bensì - in generale - un suo divisore. A meno che $n$ non sia una radice primitiva modulo $q$.

[ficus2002]

Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.

Testo nascosto, fai click qui per vederlo

Sia $d:=(n^p-n:n\in NN)$. Se $q$ è primo, allora:

• $q^2$ non divide $d$; in particolare, $d$ è square-free.
• $q|n^p-n$ per ogni $n\in ZZ$ se e solo se $q-1|p-1$.

La prima si deduce dal fatto che $q^2$ non divide $q^p-q$ ($p\ge 2$).
Per la seconda:
$(lArr)$ Se $q|n$, allora $q|n^p-n$, mentre se $(n,q)=1$, allora $n^p\equiv n(mod q)$ per Eulero-Fermat.
$(rArr)$ Viceversa, se $q|n^p-n$ per ogni $n\in ZZ$, in particolare $q|\zeta^p-\zeta$ con $\zeta$ radice primitiva di $q$. Di conseguenza, $q-1|p-1$.
Così,
$d=\prod_{q-1|p-1}q\quad$($q$ primo).