Contare soluzioni di una congruenza.
Salve,
Sto affrontando un esercizio di matematica discreta ma non riesco proprio ad incominciare, sono totalmente bloccato!
L'esercizio è questo:
Stabilire quante sono le soluzioni di $ x^26 -= 1 mod(35) $ tali che $ 0 <= x < 35 $.
Avevo già visto un esercizio simile e ho come il sentore che si possa applicare il piccolo teorema di Fermat o fare dei ragionamenti con la funzione phi di Eulero, ci ho pensato ma non mi vengono idee, sono ore che lo osservo... sarà l'ora tarda
Sto affrontando un esercizio di matematica discreta ma non riesco proprio ad incominciare, sono totalmente bloccato!
L'esercizio è questo:
Stabilire quante sono le soluzioni di $ x^26 -= 1 mod(35) $ tali che $ 0 <= x < 35 $.
Avevo già visto un esercizio simile e ho come il sentore che si possa applicare il piccolo teorema di Fermat o fare dei ragionamenti con la funzione phi di Eulero, ci ho pensato ma non mi vengono idee, sono ore che lo osservo... sarà l'ora tarda
Risposte
L'unico modo non è scomporre il modulo e andare per tentativi, vero?
Qualcuno potrebbe darmi gentilmente un'idea di come si possono risolvere esercizi di questo tipo?
Qualcuno potrebbe darmi gentilmente un'idea di come si possono risolvere esercizi di questo tipo?
up up uuuuup
Ciao!
Puoi scegliere di affrontarlo sfruttando il Teorema Cinese del Resto ("splittando" direttamente l'equazione in altre due con modulo rispettivamente 5 e 7) e il piccolo teorema di Fermat secondo cui $x^(p-1)==1 mod p$ con "p" primo oppure come hai già detto usando la funzione phi di Eulero e la generalizzazione del piccolo teorema di Fermat quando "p" non è un numero primo.
Noi facciamo un mix:
Abbiamo $x^26-=1 mod 35$, il teorema ci assicura che $ AA p $: $ x^(phi(p))-= 1 mod p $.
Calcoliamo $phi(35)=phi(5)*phi(7)=4*6=24$ da cui deduco che $x^24-=1mod 35$.
A questo punto riscrivo la nostra equazione come $x^24*x^2-=x^2-=1 mod 35$. La scelta migliore adesso è risolvere il sistema di congruenze:
$ { (x^2-=1 mod 5 ),( x^2-= 1 mod 7 ):} $ che riscrivo come: ${ (x^2-1-=0 mod 5 ),( x^2-1-= 0 mod 7 ):}$.
Sappiamo che se "p" è un numero primo che divide due fattori, allora p divide uno dei due:
${ ((x+1)(x-1)-=0 mod 5 ),( (x+1)(x-1)-= 0 mod 7 ):}$ le cui soluzioni sappiamo essere ${(x-=+-1 mod 5),(x-=+-1 mod 7):}$.
Da qui hai 2 soluzioni possibili per equazione e devi quindi valutare ogni possibile casistica accoppiandole a due a due e, una volta che trovi la soluzione globale, al variare del parametro intero vai letteralmente a "contare" le soluzioni comprese tra 0 e 35.
Spero di essere stato d'aiuto!
P.S. E' la prima risposta che do sul forum e potrei avere sbagliato un centinaio di cose su quanto detto sopra considerato che sono uno studente di informatica del primo anno e non un matematico. Se così dovesse rivelarsi chiedo venia!
Puoi scegliere di affrontarlo sfruttando il Teorema Cinese del Resto ("splittando" direttamente l'equazione in altre due con modulo rispettivamente 5 e 7) e il piccolo teorema di Fermat secondo cui $x^(p-1)==1 mod p$ con "p" primo oppure come hai già detto usando la funzione phi di Eulero e la generalizzazione del piccolo teorema di Fermat quando "p" non è un numero primo.
Noi facciamo un mix:
Abbiamo $x^26-=1 mod 35$, il teorema ci assicura che $ AA p $: $ x^(phi(p))-= 1 mod p $.
Calcoliamo $phi(35)=phi(5)*phi(7)=4*6=24$ da cui deduco che $x^24-=1mod 35$.
A questo punto riscrivo la nostra equazione come $x^24*x^2-=x^2-=1 mod 35$. La scelta migliore adesso è risolvere il sistema di congruenze:
$ { (x^2-=1 mod 5 ),( x^2-= 1 mod 7 ):} $ che riscrivo come: ${ (x^2-1-=0 mod 5 ),( x^2-1-= 0 mod 7 ):}$.
Sappiamo che se "p" è un numero primo che divide due fattori, allora p divide uno dei due:
${ ((x+1)(x-1)-=0 mod 5 ),( (x+1)(x-1)-= 0 mod 7 ):}$ le cui soluzioni sappiamo essere ${(x-=+-1 mod 5),(x-=+-1 mod 7):}$.
Da qui hai 2 soluzioni possibili per equazione e devi quindi valutare ogni possibile casistica accoppiandole a due a due e, una volta che trovi la soluzione globale, al variare del parametro intero vai letteralmente a "contare" le soluzioni comprese tra 0 e 35.
Spero di essere stato d'aiuto!
P.S. E' la prima risposta che do sul forum e potrei avere sbagliato un centinaio di cose su quanto detto sopra considerato che sono uno studente di informatica del primo anno e non un matematico. Se così dovesse rivelarsi chiedo venia!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo