Congruenze
Ciao a tutti!
Devo risolvere questo esercizio:
mostrare tutti gli interi postivi n tali che
$3^n-53$ è divisibile per 77.
Non riesco a capire da dove cominciare.. uff.. qualcuno ha qualke suggerimento ke mi "apra" la mente??
Devo risolvere questo esercizio:
mostrare tutti gli interi postivi n tali che
$3^n-53$ è divisibile per 77.
Non riesco a capire da dove cominciare.. uff.. qualcuno ha qualke suggerimento ke mi "apra" la mente??
Risposte
Qualche hint:
$77|3^n-53 Rightarrow 3^n\equiv53 mod 77$
Da qui poi fai qualche considerazione su $n$.
$77|3^n-53 Rightarrow 3^n\equiv53 mod 77$
Da qui poi fai qualche considerazione su $n$.
L'italiano... 
ehm... è da qui che non so come andare avanti...
In questo caso si tratta di risolvere un logaritmo "discreto", se cerchi bene nel forum c'è un post (che fra l'altro ho scritto io) con una ricetta per risolverlo!
In ogni caso si tratta di usare il piccolo teorema di Fermat e di fare alcune osservazioni sul simbolo di Jacobi. Prova a scrivere qualcosa, altrimenti poi ti aiuto volentieri.
A me pare che si possa risolvere senza uso di particolari teoremi, facendo vedere che $3^n -53$ non può mai essere divisibile per $7$. Pertanto non sarà divisibile nemmeno per $77$.
Come inizio potresti provare a studiare come si comportano le potenze di $3$, rispetto alla divisione per $7$.
Come inizio potresti provare a studiare come si comportano le potenze di $3$, rispetto alla divisione per $7$.
"robbstark":
A me pare che si possa risolvere senza uso di particolari teoremi, facendo vedere che $3^n -53$ non può mai essere divisibile per $7$.
81 - 53 = 28
In ogni caso, forse studiarsi separatamente le congruenze modulo 7 e modulo 11 semplificherebbe i calcoli...
Sì, avevo sbagliato una sottrazione, in realtà può essere divisibile per 7. Comunque l'idea era questa di studiare le 2 classi resto 7 e 11 e mettere insieme i risultati.
L'idea è corretta ed è il punto di inizio:
${(3^n\equiv53(7)),(3^n\equiv53(11)):} Rightarrow {(3^n\equiv-3(7)),(3^n\equiv-2(11)):} Rightarrow {(3^(n-1)\equiv-1(7)),(3^n\equiv9(11)):}$
La seconda ha come soluzione $n=2+k*phi(11)$ ricordando che $x^(phi(11))\equiv 1 (11)$, mentre la prima:
$3^n\equiv-3(7) Rightarrow 3^(n-1)\equiv -1(7) Rightarrow 3^(n-1)\equiv 3*2 (7) Rightarrow 3^(n-2)\equiv2(7) Rightarrow 3^(n-2)\equiv 9 (7)$
da cui $n-2 \equiv 2(phi(7))$, da qui ti lascio volentieri concludere.
P.S: le parentesi sottointendono il modulo.
${(3^n\equiv53(7)),(3^n\equiv53(11)):} Rightarrow {(3^n\equiv-3(7)),(3^n\equiv-2(11)):} Rightarrow {(3^(n-1)\equiv-1(7)),(3^n\equiv9(11)):}$
La seconda ha come soluzione $n=2+k*phi(11)$ ricordando che $x^(phi(11))\equiv 1 (11)$, mentre la prima:
$3^n\equiv-3(7) Rightarrow 3^(n-1)\equiv -1(7) Rightarrow 3^(n-1)\equiv 3*2 (7) Rightarrow 3^(n-2)\equiv2(7) Rightarrow 3^(n-2)\equiv 9 (7)$
da cui $n-2 \equiv 2(phi(7))$, da qui ti lascio volentieri concludere.
P.S: le parentesi sottointendono il modulo.
.. ma $\phi$ cosa intende?
"dustofstar":
.. ma $\phi$ cosa intende?
E' la funzione di Eulero $phi(x)$, ovvero il numero di numeri minori di $x$ e coprimi con $x$
.. uff.. io ci sto provando.. ma.. non riesco a capire come devo applicare fermat.. e come utilizzare il simbolo di jacobi..
"Lord K":
L'idea è corretta ed è il punto di inizio:
${(3^n\equiv53(7)),(3^n\equiv53(11)):} Rightarrow {(3^n\equiv-3(7)),(3^n\equiv-2(11)):} Rightarrow {(3^(n-1)\equiv-1(7)),(3^n\equiv9(11)):}$
La seconda ha come soluzione $n=2+k*phi(11)$ ricordando che $x^(phi(11))\equiv 1 (11)$, .
allora... con un po' piu' di attenzione la mia mente comincia ad aprirsi... uff.. pero'... non sono d'accordo con la soluzione della seconda. che la soluzione sia $n=2+k*phi(11)$ non sarebbe vero solo se 3 fosse radice primitiva mod 11?? Questo non e' vero , perche' $3^5\equiv1(mod11)$ e $5!=phi(11)=10$
Potrei invece dire che se $3^n\equiv3^2(mod11)$ allora n deve essere $n\equiv2(mod5)$ dove 5 e' l'ordine di 3 mod 11?
Non so..ricordo di poter applicare questa.. ma.. non so da quale cassetto della memoria l'ho tirata fuori..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo