Sistema di Congruenze Parametrico

[dondolando]

Ciao a tutti! Io (e parte del mio corso universitario) domani abbiamo un esame e ci siamo imbattuti in questo esercizio, scervellandoci su di esso senza risultati concreti, posto la consegna e i miei ragionamenti e se potete darmi una mano sarebbe un grandissimo aiuto!

Ho il sistema ${( ax-=-3 (mod 17) ),( a^x-=4 (mod 17) ):}$
Viene chiesto per quali valori di $a$ tale sistema è risolubile. Per la prima equazione basta che $MCD(a,17)|-3$.
La seconda mi lascia un pò spiazzato: Sicuramente $a$ non deve essere un multiplo di 17.
Ad occhio si vede che $a-=+-2 mod 17$ ed $x-=2 (mod phi(17)=16)$ è soluzione. (Dubbio: E' giusta come osservazione $x-=2 (mod phi(17)=16)$? Perchè in teoria questa dovrebbe essere la condizione sufficiente per il Teorema di Eulero se ho dedotto bene.)
Stesso vale per $a-=4 (mod 17)$ ed $x-=1 (mod 16).$ Ma per poter dare una risposta certa che queste sono tutte e sole le soluzioni dovrei in un certo senso escludere che in $ZZ_17$ ci siano altri elementi che elevati a "qualcosa" siano congrui a 4 modulo 17 e non mi sembra ragionevole provare tutte le potenze di ogni elemento .

Esiste un modo più "algoritmico" di procedere ed essere sicuri di beccare tutte le soluzioni? C'è qualche errore nel ragionamento proposto e/o qualche conoscenza/finezza teorica che mi manca e potrebbe aiutare ad escludere elementi che sicuramente non fanno parte delle soluzioni?

[Martino]

Ti suggerisco di scrivere $x=16c+d$ con $d$ tra 0 e 15. Ottieni che $a^d$ vale 4 modulo 17 e questo può succedere solo se 4 sta nel gruppo moltiplicativo generato da $a$.

[dondolando]

Intanto grazie mille della risposta. Il gruppo moltiplicativo sarebbe brutalmente la classica "tabella" con tutti gli elementi in $ZZ_17$ con il relativo inverso, giusto? Perché diversamente mi sfugge a cosa ti riferisci, o peggio non l'ho affrontato nel corso di matematica discreta ed algebra lineare. Potresti spiegarmi operativamente come funziona? Magari afferro meglio il concetto.

Ottieni che $a^d$ vale 4 modulo 17 e questo può succedere solo se 4 sta nel gruppo moltiplicativo generato da $a$.

Gentilmente sapresti dirmi come mai questo accade?

[Martino]

Sì parlo della tabella moltiplicativa, cioè la tabella del gruppo moltiplicativo degli elementi non nulli di \( \displaystyle \mathbb{Z}/17\mathbb{Z} \) . Le possibilità per $d$ le ottieni da tale tabella moltiplicativa.

Una volta ottenuto $d$ ottieni i valori di $a$ sempre da tale tabella.

Osserva che $a^(16)$ è congruo a 1 modulo 17 (se 17 non divide $a$). Questo è sostanzialmente per il piccolo teorema di Fermat.

Occhio perché la prima equazione che hai scritto dà come unica condizione che 17 non divide $a$.

Non riesco a risponderti meglio perché sono da cellulare, ma credo di averti dato tutti gli elementi.

[dondolando]

No anzi grazie del fatto che rispondi nonostante sia fuori. Il fatto è che proprio mi manca la nozione che stai sfruttando, non seguo il filo logico. Cioè non colgo la relazione tra il gruppo moltiplicativo di $ZZ_17$ e $d$, e come dovrei trovare $d$ in funzione della tabella che sto costruendo, in quello che ho studiato non c'è niente del genere e su internet sto avendo difficoltà a trovare accenni all'argomento. Non so neanche se stia facendo bene a costruirla, la tabella, che comunque prende un pò di tempo che in sede di esame non avrei, quindi a maggior ragione deve esserci qualcos altro che mi sfugge.

[Martino]

Di sicuro esiste un modo più intelligente, ma io non so che risultati hai visto nel corso e tutto dipende molto da questo.

Una volta risolto l'esercizio (in qualunque modo) ti verranno in mente scorciatoie. Secondo me in generale è una pessima idea studiare solo in funzione dell'esame.

[dondolando]

Sono perfettamente d'accordo. Non studio solo in funzione dell'esame, è da circa 4 mesi che lo preparo e qualsiasi dispensa e/o fonte alternativa che possa aiutarmi alla comprensione dell'argomento l'ho consultata. Infatti ho cercato anche altrove su internet qualche dispensa sull'argomento, è solo che non trovando le informazioni che mi servono riguardo al metodo da te proposto da nessuna parte, fino ad adesso l'esercizio rimane irrisolto. Di modo per risolverlo non ne conosco neanche uno se non quello di scrivermi tutte le potenze modulo 17 di tutti i numeri da 0 a 16.. Non capisco il metodo col gruppo moltiplicativo, grazie comunque molte della tua disponibilità!