Divisibilità
Buon pomeriggio! Un esercizio mi chiede di:
Ho iniziato così:
$15 | n^16 +14n^4 +2n + 1 Leftrightarrow [n^16 +14n^4 +2n]_15 = [-1]_15 Leftrightarrow [n^16 +14n^4 +2n]_15 = [14]_15 Leftrightarrow [n^16]_15 +[14n^4]_15 +[2n]_15 = [14]_15 Leftrightarrow [n]_15 +[14n^4]_15 +[2n]_15 = [14]_15 Leftrightarrow [14n^4 +3n]_15 = [14]_15$
Come posso proseguire?
Determinare quali numeri della forma $n^16 +14n^4 +2n + 1, n in N$ sono divisibili per 15
Ho iniziato così:
$15 | n^16 +14n^4 +2n + 1 Leftrightarrow [n^16 +14n^4 +2n]_15 = [-1]_15 Leftrightarrow [n^16 +14n^4 +2n]_15 = [14]_15 Leftrightarrow [n^16]_15 +[14n^4]_15 +[2n]_15 = [14]_15 Leftrightarrow [n]_15 +[14n^4]_15 +[2n]_15 = [14]_15 Leftrightarrow [14n^4 +3n]_15 = [14]_15$
Come posso proseguire?
Risposte
In base a cosa hai sostituito $n^{16}$ con $n$?
Ti consiglio di osservare che $n$ dev'essere per forza coprimo con $15$ e applicare il teorema di Eulero-Fermat [tex]n^{\varphi(15)} \equiv 1 \mod 15[/tex].
Ti consiglio di osservare che $n$ dev'essere per forza coprimo con $15$ e applicare il teorema di Eulero-Fermat [tex]n^{\varphi(15)} \equiv 1 \mod 15[/tex].
Perché devono essere coprimi?
Perché se non fossero coprimi allora esisterebbe un fattore $m>1$ che divide entrambi tale che $m| n^{16}+14n^4+2n$ ma non divide $n^{16}+14n^4+2n+1$ che per richiesta deve essere divisibile per $15$, assurdo...
Capito... quindi, io avrei $varphi(15) = varphi(3)varphi(5)=2*4=8$, dunque, $n^16$ $\equiv$ $n^7 mod 15$, da cui ottengo:
$[n^7 +14n^4 + 2n]_15 = [14]_15$
Giusto? Poi come posso procedere? (Scusate, è la prima volta che affronto questo tipo di esercizi e non so bene come si proceda!)
$[n^7 +14n^4 + 2n]_15 = [14]_15$
Giusto? Poi come posso procedere? (Scusate, è la prima volta che affronto questo tipo di esercizi e non so bene come si proceda!)
Partiamo da $n^{16}$, 16 è un multiplo di $\varphi(15)=8$ quindi $[n^{16}]=[1]$, questo vale in generale, se $m$ è multiplo di $\varphi(n)$ allora $a^m-= 1 \mod n$.
Quindi $[n^{16}]+[14n^4]+[2n]+[1]=[1]+[14n^4]+[2n]+[1]=[2]+[14n^4]+[2n]$
Ora passiamo a $14n^4$, abbiamo che $n^4-= \pm 1 \mod 15$ poiché $n^{8}-1=(n^4-1)(n^4+1) \mod 15$, quindi abbiamo due casi $[14n^4]=[14]$ e $[14n^4]=[-14]$, studiamoli separatamente:
Caso 1) $14+2+2n=16+2n-=1+2n-= 0 \mod 15$ da cui $2n-=-1 \mod 15$, e quindi moltiplicando per 8 otteniamo $16n-=n-=-8-= 7 \mod 15$, quindi un insieme di soluzioni è dato da ${n=7+15k, k \in ZZ}$
Caso 2) questo caso è da escludere perché $n^4=(n^2)^2-=1 \mod 3$ per Fermat o anche deve valere che $n^4 -= 1 \mod 5$ sempre per fermat
Quindi $[n^{16}]+[14n^4]+[2n]+[1]=[1]+[14n^4]+[2n]+[1]=[2]+[14n^4]+[2n]$
Ora passiamo a $14n^4$, abbiamo che $n^4-= \pm 1 \mod 15$ poiché $n^{8}-1=(n^4-1)(n^4+1) \mod 15$, quindi abbiamo due casi $[14n^4]=[14]$ e $[14n^4]=[-14]$, studiamoli separatamente:
Caso 1) $14+2+2n=16+2n-=1+2n-= 0 \mod 15$ da cui $2n-=-1 \mod 15$, e quindi moltiplicando per 8 otteniamo $16n-=n-=-8-= 7 \mod 15$, quindi un insieme di soluzioni è dato da ${n=7+15k, k \in ZZ}$
Caso 2) questo caso è da escludere perché $n^4=(n^2)^2-=1 \mod 3$ per Fermat o anche deve valere che $n^4 -= 1 \mod 5$ sempre per fermat
"dan95":Come giustifichi questo? A priori potrebbe aversi [tex]n^4-1 \equiv 3[/tex] e [tex]n^4+1 \equiv 5[/tex].
$n^{8}-1=(n^4-1)(n^4+1) \mod 15$, quindi abbiamo due casi $[14n^4]=[14]$ e $[14n^4]=[-14]$
Eh l'ho modificato proprio ora, grazie Martino 
A priori potrebbe aversi [tex]n^4-1 \equiv 3[/tex] e [tex]n^4+1 \equiv 5[/tex] no?
$n^4+1-=5 \mod 15$ significa che $15 | n^4+1-5$ in particolare $5| n^4+1-5$ da cui $5| n^4+1$, ma questo non è possibile perché $(n,15)=1$ quindi $(n,5)=1$ dunque per Fermat risulta $n^4-= 1 \mod 5$
Grazie mille per l'aiuto!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo