Esercizio congruenza con potenze. Forti dubbi
Ho questo quesito.
a) Determinare tutti i numeri interi $n$ tali che $77| 4^(n^2+n+13)-1$
b) Determinare un primo dispari $p$ tale che , $AA n $ , $p$ non divida $ 4^(n^2+n+13)-1$.
E' la prima volta che vedo una cosa del genere , dato che a lezione abbiamo sempre lavorato con congruenze lineari, ma ci provo lo stesso, anche perché penso ci sia qualche trucchetto. Datemi smentite o dritte
L'ho svolto cosi .
Punto a)
La condizione $77| 4^(n^2+n+13)-1$ equivale a dire che
$4^(n^2+n+13)-1-=0(mod77) => 4^(n^2+n+13)-=1(mod77)$ (1)
Si verifica ora facilmente che $77=4(19)+1$ e cioè che
$(77,4)=1 =>$ $4,77$ relativamente primi. Ora poiché $77=7*11$ per il teorema fondamentale dell'aritmetica, segue che $\phi(77) = (7-1)(11-1)=60$ ove per $\phi$ intendo la funzione di Eulero.
Dunque,dal teorema di Eulero Fermat segue che $4^(\phi(77))-=1(mod77)$
Quindi se voglio che valga la (1), deve risultare che $\phi(77)=60| n^2+n+13 => n^2+n+13-=0(mod60)$ (2)
Ora poiché $60=2^2*3*5$ segue che la (2) è equivalente , per la seconda formulazione del teorema cinese del resto, trovare $n in ZZ$ risolventi il seguente sistema cinese :
$n^2+n+13-=n^2+n+1-=0(mod4)$
$n^2+n+13-=n^2+n+1-=0(mod3)$
$n^2+n+13-=n^2+n+3-=0(mod5)$
Ora noto che per
$n=0 => 1-=0(mod4)$ assurdo
$n=1 => 1+1+1-=3(mod4)$ <-- 1 non è soluzione della prima.
$n=2 => 4+2+1-=3(mod4) $ <-- 2 non è soluzione della prima
$n=3 => 9+3+1-=13-=1(mod4) $ <--3 non è soluzione della prima.
Quindi Ogni $n in ZZ_4$ non è soluzione della prima, quindi la prima congruenza è in compatibile. Di conseguenza risulta che l'intero sistema non ammette soluzione, giusto?!
Quindi non esiste $n $ tale che $77|4^(n^2+n+13)-1$
b) direi che $p=5$ va bene.
Infatti se $5|4^(n^2+n+13)-1=> 4^(n^2+n+13)-=1(mod5)$ (1)
Ora $(4,5)=1$ quindi per fermat $4^4-=1(mod5)$
Quindi se vale la 1, deve succedere che
$4| n^2+n+13$ ma abbiamo già detto che non è possibile.
Quindi $p=5$ è il primo dispari cercato.
Come vi sembra?
Grazie per una vostra eventuale risposta.
a) Determinare tutti i numeri interi $n$ tali che $77| 4^(n^2+n+13)-1$
b) Determinare un primo dispari $p$ tale che , $AA n $ , $p$ non divida $ 4^(n^2+n+13)-1$.
E' la prima volta che vedo una cosa del genere , dato che a lezione abbiamo sempre lavorato con congruenze lineari, ma ci provo lo stesso, anche perché penso ci sia qualche trucchetto. Datemi smentite o dritte
L'ho svolto cosi .
Punto a)
La condizione $77| 4^(n^2+n+13)-1$ equivale a dire che
$4^(n^2+n+13)-1-=0(mod77) => 4^(n^2+n+13)-=1(mod77)$ (1)
Si verifica ora facilmente che $77=4(19)+1$ e cioè che
$(77,4)=1 =>$ $4,77$ relativamente primi. Ora poiché $77=7*11$ per il teorema fondamentale dell'aritmetica, segue che $\phi(77) = (7-1)(11-1)=60$ ove per $\phi$ intendo la funzione di Eulero.
Dunque,dal teorema di Eulero Fermat segue che $4^(\phi(77))-=1(mod77)$
Quindi se voglio che valga la (1), deve risultare che $\phi(77)=60| n^2+n+13 => n^2+n+13-=0(mod60)$ (2)
Ora poiché $60=2^2*3*5$ segue che la (2) è equivalente , per la seconda formulazione del teorema cinese del resto, trovare $n in ZZ$ risolventi il seguente sistema cinese :
$n^2+n+13-=n^2+n+1-=0(mod4)$
$n^2+n+13-=n^2+n+1-=0(mod3)$
$n^2+n+13-=n^2+n+3-=0(mod5)$
Ora noto che per
$n=0 => 1-=0(mod4)$ assurdo
$n=1 => 1+1+1-=3(mod4)$ <-- 1 non è soluzione della prima.
$n=2 => 4+2+1-=3(mod4) $ <-- 2 non è soluzione della prima
$n=3 => 9+3+1-=13-=1(mod4) $ <--3 non è soluzione della prima.
Quindi Ogni $n in ZZ_4$ non è soluzione della prima, quindi la prima congruenza è in compatibile. Di conseguenza risulta che l'intero sistema non ammette soluzione, giusto?!
Quindi non esiste $n $ tale che $77|4^(n^2+n+13)-1$
b) direi che $p=5$ va bene.
Infatti se $5|4^(n^2+n+13)-1=> 4^(n^2+n+13)-=1(mod5)$ (1)
Ora $(4,5)=1$ quindi per fermat $4^4-=1(mod5)$
Quindi se vale la 1, deve succedere che
$4| n^2+n+13$ ma abbiamo già detto che non è possibile.
Quindi $p=5$ è il primo dispari cercato.
Come vi sembra?
Grazie per una vostra eventuale risposta.
Risposte
Per il punto a), direi che hai fatto tutto bene.
Però mi sembra eccessivo "scomodare" il teorema cinese del resto per dimostrare che $60$ non divide $n^2+n+13$.
Basta dire che $n^2+n$ è sempre pari, dunque $n^2+n+13$ è sempre dispari, dunque $60$ non lo può dividere.
Il punto b) mi sembra correttissimo.
Però mi sembra eccessivo "scomodare" il teorema cinese del resto per dimostrare che $60$ non divide $n^2+n+13$.
Basta dire che $n^2+n$ è sempre pari, dunque $n^2+n+13$ è sempre dispari, dunque $60$ non lo può dividere.
Il punto b) mi sembra correttissimo.
Ho capito , grazie Gi8!
EDIT
Uhm una cosa, come si può affermare che $n^2+n$ è sempre pari?
Deriva dal fatto che $2| n^2+n , AA n$, giusto?
Se volessimo dimostrarlo ho che otterrei che $ [n^2+n]_2 =[0]_2$che è vera $AA n in ZZ_2$ quindi quel numero è sicuramente pari, quindi se pari non può essere dispari.
poi essendo $13-=1(mod2)$ segue banalmente che se $n^2+n-=0(mod 2)$ se supponiamo per assurdo che $n^2+n+13-=0(mod2)=> 1-=0(mod2) $ <-- assurdo. Quindi non essendo pari, è sicuramente dispari.
Giusto?
Quindi se quel numero è dispari,essendo sessanta pari, segue banalmente che 60 non può dividere quel numero.
Da qui potrei trarre una considerazione generale . Del tipo : Nessun $n$ pari divide $z$ dispari.
Infatti supponiamo per assurdo che un numero pari dividesse un'altro dispari.
Assumiamo che $n= 2k $ e che $z=2k+1$ ,dispari, $k in ZZ$.
Abbiamo che $n|z => 2k|2k+1=> 2k+1-=0(mod2k)=>1-=0(mod2k)$ . Che è l'assurdo voluto.
Questa proposizione invece non si può invertire.
Infatti $5|10$ ove 5 è dispari mentre 10 è pari!
Fammi sapere che ne pensi
EDIT
Uhm una cosa, come si può affermare che $n^2+n$ è sempre pari?
Deriva dal fatto che $2| n^2+n , AA n$, giusto?
Se volessimo dimostrarlo ho che otterrei che $ [n^2+n]_2 =[0]_2$che è vera $AA n in ZZ_2$ quindi quel numero è sicuramente pari, quindi se pari non può essere dispari.
poi essendo $13-=1(mod2)$ segue banalmente che se $n^2+n-=0(mod 2)$ se supponiamo per assurdo che $n^2+n+13-=0(mod2)=> 1-=0(mod2) $ <-- assurdo. Quindi non essendo pari, è sicuramente dispari.
Giusto?
Quindi se quel numero è dispari,essendo sessanta pari, segue banalmente che 60 non può dividere quel numero.
Da qui potrei trarre una considerazione generale . Del tipo : Nessun $n$ pari divide $z$ dispari.
Infatti supponiamo per assurdo che un numero pari dividesse un'altro dispari.
Assumiamo che $n= 2k $ e che $z=2k+1$ ,dispari, $k in ZZ$.
Abbiamo che $n|z => 2k|2k+1=> 2k+1-=0(mod2k)=>1-=0(mod2k)$ . Che è l'assurdo voluto.
Questa proposizione invece non si può invertire.
Infatti $5|10$ ove 5 è dispari mentre 10 è pari!
Fammi sapere che ne pensi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo