Esercizi equazioni diofantee e congruenze
Innanzitutto buona giornata a tutti.
Ho i seguenti esercizi da risolvere:
Per il primo procedo così:
[tex]486x+360y=54[/tex]
Tale equazione è risolubile se e solo se l'M.C.D tra [tex]486[/tex] e [tex]360[/tex] divide [tex]54[/tex].
Calcolo l'MCD tra i due valori:
[tex]486=360\cdot 1 +126[/tex]
[tex]360=126\cdot 2 +108[/tex]
[tex]126=108\cdot 1 +18[/tex]
[tex]108=18 \cdot 6[/tex]
ottengo quindi che l'MCD tra i due vale [tex]8[/tex] ed essendo che [tex]8\mid 54[/tex] so che l'equazione è risolvibile.
A questo punto pongo [tex]a=486 \wedge b=360[/tex] e procedo nel seguente modo:
[tex]126=a-b[/tex]
[tex]108=b-2a+2b=3b-2a[/tex]
[tex]18=a-b-3b+2a=3a-4b[/tex]
ottengo quindi che per l'identità di Bezout posti [tex]s=3 \wedge t=-4[/tex][tex]486s+360t=18[/tex] ed essendo [tex]54=3 \cdot 18[/tex] ottengo quindi [tex]{x}_{0}=9 \wedge {y}_{0}=-12[/tex].
Ottengo poi che tutte le soluzioni cercate sono della forma [tex]{x}_{k}=9+20k[/tex] e [tex]{y}_{k}=-12-27k[/tex] con [tex]k \in \mathbb{Z}[/tex].
Per il secondo esercizio ho che
[tex]126x \equiv 54 (mod[/tex] [tex]360)[/tex]
che è equivalente all'equazione diofantea [tex]-360t+126s=54[/tex]
sfruttando quanto calcolato prima ho che MCD tra [tex]-360[/tex] e [tex]126[/tex] è 18 e posti [tex]a=-360[/tex] e [tex]b=126[/tex] procedo nel seguente modo:
[tex]108=-a-2b[/tex]
[tex]18=b+a+2b=3b+a[/tex]
quindi ottengo quali soluzioni dell'equazione diofantea [tex]{t}_{0}=3 \wedge {s}_{0}=9[/tex] e quindi tutte le soluzioni sono della forma [tex]{t}_{k}=3+7k \wedge {s}_{k}=9+20k[/tex] con [tex]k \in \mathbb{Z}[/tex].
Concludo quindi che tutte le soluzioni intere della congruenza lineare iniziale sono della forma [tex]{x}_{k}=9+20k[/tex] con [tex]k \in \mathbb{Z}[/tex].
Per il terzo esercizio non sono molto sicuro su come procedere:
innanzitutto so che la congruenza [tex]\left[ a \right]_{360} \left[x\right]_{360}=\left[1\right]_{360}[/tex] ammette soluzioni se e solo se [tex]a[/tex] e [tex]360[/tex] sono tra loro coprimi, quindi esisterà una soluzione a tale congruenza per ogni valore appartenente all'insieme degli elementi invertibili di [tex]{\mathbb{Z}}_{360}[/tex] ovvero l'insieme costituito da tutte le classi di resto tali per cui i rappresentati delle stesse siano coprimi con [tex]360[/tex].
Il numero degli elementi soppongo si trovi mediante la funzione o indicatore di Eulero ovvero [tex][/tex] [tex]\varphi(360)=\varphi(2^3 \cdot 3^2 \cdot 5)=2^2 \cdot 3 \cdot 2 \cdot 4=96[/tex] quindi ci saranno [tex]96[/tex] possibili classi di resto che ammettono soluzione in questo tipo di congruenza.
Il quarto esercizio richiede di calcolare la potenza [tex]13^{99} (mod[/tex] [tex]360)[/tex] ovvero:
per il teorema di Eulero so che [tex]a^{\varphi(n)} \equiv 1 (mod[/tex] [tex]n)[/tex] quindi ho nel mio caso
[tex]13^{99} = 13^{96}\cdot 13^3 \equiv 13^3 (mod[/tex] [tex]360)[/tex] e calcolando [tex]13^3=2097[/tex] e facendo la divisione tra quest'ultimo e [tex]360[/tex] ottengo che [tex]13^{99} \equiv 37 (mod[/tex] [tex]360)[/tex]
Non riesco invece ad interpretare i seguenti due esercizi:
Per questo esercizio so che [tex]\varphi(12)=4[/tex], quindi che [tex]x^{4} \equiv 1 (mod[/tex] [tex]12)[/tex], segue che allora [tex]x^4 \equiv x^2 (mod[/tex] [tex]12)[/tex] ma una volta detto questo? Mi sembra riduttivo dire che abbia quattro suluzioni perchè l'indicatore di Eulero con argomento [tex]12[/tex] da come risultato quattro, o no?
Per quest'ultimo invece come capisco che tale congruenza ha infinite soluzioni? mi basta dire che essendo il coefficiente che moltiplica la variabile [tex]x[/tex] uguale a [tex]1[/tex] e quindi coprimo con [tex]12[/tex] tale eqauzione ammette sicuramente soluzioni essendo che [tex]1 \mid 5[/tex]?
Sono abbastanza confuso su queste ultime due e sulle congruenze che hanno una variabile elevata a qualcosa, esercizi che semmai dopo posto.
Per ora vi ringrazio di ogni delucidazione.
Ed ancora buona giornata.
Ho i seguenti esercizi da risolvere:
Per il primo procedo così:
[tex]486x+360y=54[/tex]
Tale equazione è risolubile se e solo se l'M.C.D tra [tex]486[/tex] e [tex]360[/tex] divide [tex]54[/tex].
Calcolo l'MCD tra i due valori:
[tex]486=360\cdot 1 +126[/tex]
[tex]360=126\cdot 2 +108[/tex]
[tex]126=108\cdot 1 +18[/tex]
[tex]108=18 \cdot 6[/tex]
ottengo quindi che l'MCD tra i due vale [tex]8[/tex] ed essendo che [tex]8\mid 54[/tex] so che l'equazione è risolvibile.
A questo punto pongo [tex]a=486 \wedge b=360[/tex] e procedo nel seguente modo:
[tex]126=a-b[/tex]
[tex]108=b-2a+2b=3b-2a[/tex]
[tex]18=a-b-3b+2a=3a-4b[/tex]
ottengo quindi che per l'identità di Bezout posti [tex]s=3 \wedge t=-4[/tex][tex]486s+360t=18[/tex] ed essendo [tex]54=3 \cdot 18[/tex] ottengo quindi [tex]{x}_{0}=9 \wedge {y}_{0}=-12[/tex].
Ottengo poi che tutte le soluzioni cercate sono della forma [tex]{x}_{k}=9+20k[/tex] e [tex]{y}_{k}=-12-27k[/tex] con [tex]k \in \mathbb{Z}[/tex].
Per il secondo esercizio ho che
[tex]126x \equiv 54 (mod[/tex] [tex]360)[/tex]
che è equivalente all'equazione diofantea [tex]-360t+126s=54[/tex]
sfruttando quanto calcolato prima ho che MCD tra [tex]-360[/tex] e [tex]126[/tex] è 18 e posti [tex]a=-360[/tex] e [tex]b=126[/tex] procedo nel seguente modo:
[tex]108=-a-2b[/tex]
[tex]18=b+a+2b=3b+a[/tex]
quindi ottengo quali soluzioni dell'equazione diofantea [tex]{t}_{0}=3 \wedge {s}_{0}=9[/tex] e quindi tutte le soluzioni sono della forma [tex]{t}_{k}=3+7k \wedge {s}_{k}=9+20k[/tex] con [tex]k \in \mathbb{Z}[/tex].
Concludo quindi che tutte le soluzioni intere della congruenza lineare iniziale sono della forma [tex]{x}_{k}=9+20k[/tex] con [tex]k \in \mathbb{Z}[/tex].
Per il terzo esercizio non sono molto sicuro su come procedere:
innanzitutto so che la congruenza [tex]\left[ a \right]_{360} \left[x\right]_{360}=\left[1\right]_{360}[/tex] ammette soluzioni se e solo se [tex]a[/tex] e [tex]360[/tex] sono tra loro coprimi, quindi esisterà una soluzione a tale congruenza per ogni valore appartenente all'insieme degli elementi invertibili di [tex]{\mathbb{Z}}_{360}[/tex] ovvero l'insieme costituito da tutte le classi di resto tali per cui i rappresentati delle stesse siano coprimi con [tex]360[/tex].
Il numero degli elementi soppongo si trovi mediante la funzione o indicatore di Eulero ovvero [tex][/tex] [tex]\varphi(360)=\varphi(2^3 \cdot 3^2 \cdot 5)=2^2 \cdot 3 \cdot 2 \cdot 4=96[/tex] quindi ci saranno [tex]96[/tex] possibili classi di resto che ammettono soluzione in questo tipo di congruenza.
Il quarto esercizio richiede di calcolare la potenza [tex]13^{99} (mod[/tex] [tex]360)[/tex] ovvero:
per il teorema di Eulero so che [tex]a^{\varphi(n)} \equiv 1 (mod[/tex] [tex]n)[/tex] quindi ho nel mio caso
[tex]13^{99} = 13^{96}\cdot 13^3 \equiv 13^3 (mod[/tex] [tex]360)[/tex] e calcolando [tex]13^3=2097[/tex] e facendo la divisione tra quest'ultimo e [tex]360[/tex] ottengo che [tex]13^{99} \equiv 37 (mod[/tex] [tex]360)[/tex]
Non riesco invece ad interpretare i seguenti due esercizi:
Per questo esercizio so che [tex]\varphi(12)=4[/tex], quindi che [tex]x^{4} \equiv 1 (mod[/tex] [tex]12)[/tex], segue che allora [tex]x^4 \equiv x^2 (mod[/tex] [tex]12)[/tex] ma una volta detto questo? Mi sembra riduttivo dire che abbia quattro suluzioni perchè l'indicatore di Eulero con argomento [tex]12[/tex] da come risultato quattro, o no?
Per quest'ultimo invece come capisco che tale congruenza ha infinite soluzioni? mi basta dire che essendo il coefficiente che moltiplica la variabile [tex]x[/tex] uguale a [tex]1[/tex] e quindi coprimo con [tex]12[/tex] tale eqauzione ammette sicuramente soluzioni essendo che [tex]1 \mid 5[/tex]?
Sono abbastanza confuso su queste ultime due e sulle congruenze che hanno una variabile elevata a qualcosa, esercizi che semmai dopo posto.
Per ora vi ringrazio di ogni delucidazione.
Ed ancora buona giornata.
Risposte
Riguardo il penultimo esercizio, devi considerare che se $n$ è un numero primo $(ZZ_n,+,*)$ è un campo in cui ogni elemento non nullo ammette inverso moltiplicativo, mentre se $n$ non è un numero primo allora si ha un anello commutativo unitario dove gli inversi moltiplicativi hanno cardinalità $phi(n)$, cioè la funzione di Eulero.
$phi(12)=4$ quindi $[x]^6 _12=[1]_12$ ha quattro soluzioni che sono le classi dei resti coprime con $12$: $[1],[5],[7],[11]$.
$phi(12)=4$ quindi $[x]^6 _12=[1]_12$ ha quattro soluzioni che sono le classi dei resti coprime con $12$: $[1],[5],[7],[11]$.
L'ultimo esercizio dovrebbe essere come il penultimo:
dal fatto che se $(a,12)=1$ e $EEr in ZZ | r-=1_(mod phi(12)) => a^r -=a_(mod 12)$, quindi dovrebbe essere $[x]^5 _12=[5]_12$, in quanto $AAa in [5]_12$ si ha che $4|a^5 - 5$
dal fatto che se $(a,12)=1$ e $EEr in ZZ | r-=1_(mod phi(12)) => a^r -=a_(mod 12)$, quindi dovrebbe essere $[x]^5 _12=[5]_12$, in quanto $AAa in [5]_12$ si ha che $4|a^5 - 5$
Innanzitutto ti ringrazio.
Non mi è chiaro il seguente passaggio dell'ultimo esercizio: [tex]\exists{r}\in\mathbb{Z}{\mid}{r}\equiv{1}_{{\text{mod}\phi{\left({12}\right)}}}\Rightarrow{{a}}^{{r}}\equiv{a}_{{\text{mod}{12}}}[/tex] da dove prendi che r è congruo 1 modulo indicatore di Eulero con argomento 12?
Per quanto riguarda invece i seguenti esercizi:
Per il primo, secondo quanto enunciato dal teorema di Eulero, ovvero [tex]a^{\varphi(n)} \equiv {1}_{mod}n[/tex] posso concludere che [tex]9^{\varphi(35)} \equiv {1}_{mod}35 \Rightarrow 9^{24} \equiv {1}_{mod}35[/tex].
La seconda equazione ammette invece soluzione se e solo se l'MCD tra [tex]a[/tex] ed [tex]n[/tex] è uguale ad [tex]1[/tex], ovvero per ogni elemento invertibile appartenente all'insieme quoziente [tex]{\mathbb{Z}}_{n}[/tex] la congruenza data ammette soluzione e sempre per il teorema di Eulero la sua soluzione è [tex]x=\varphi(n)[/tex].
Per la terza congruenza ho che essendo 7 un numero primo e la struttura algebrica formata da [tex]{\mathbb{Z}}_{7}[/tex] privato di [tex]{\left [0\right]}_{7}[/tex] e dall'operazione prodotto [tex]\cdot[/tex] un gruppo abeliano ogni elemento di tale insieme quoziente ammette inverso.
Le soluzioni possibili sono pertanto le seguenti:
[tex]{\left [1 \right]}_{7} \cdot {\left [ 1\right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [2 \right]}_{7} \cdot {\left [4 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [3 \right]}_{7} \cdot {\left [5 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [4 \right]}_{7} \cdot {\left [2 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [5 \right]}_{7} \cdot {\left [3 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [6 \right]}_{7} \cdot {\left [6 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
Grazie mille ancora!!
Non mi è chiaro il seguente passaggio dell'ultimo esercizio: [tex]\exists{r}\in\mathbb{Z}{\mid}{r}\equiv{1}_{{\text{mod}\phi{\left({12}\right)}}}\Rightarrow{{a}}^{{r}}\equiv{a}_{{\text{mod}{12}}}[/tex] da dove prendi che r è congruo 1 modulo indicatore di Eulero con argomento 12?
Per quanto riguarda invece i seguenti esercizi:
Per il primo, secondo quanto enunciato dal teorema di Eulero, ovvero [tex]a^{\varphi(n)} \equiv {1}_{mod}n[/tex] posso concludere che [tex]9^{\varphi(35)} \equiv {1}_{mod}35 \Rightarrow 9^{24} \equiv {1}_{mod}35[/tex].
La seconda equazione ammette invece soluzione se e solo se l'MCD tra [tex]a[/tex] ed [tex]n[/tex] è uguale ad [tex]1[/tex], ovvero per ogni elemento invertibile appartenente all'insieme quoziente [tex]{\mathbb{Z}}_{n}[/tex] la congruenza data ammette soluzione e sempre per il teorema di Eulero la sua soluzione è [tex]x=\varphi(n)[/tex].
Per la terza congruenza ho che essendo 7 un numero primo e la struttura algebrica formata da [tex]{\mathbb{Z}}_{7}[/tex] privato di [tex]{\left [0\right]}_{7}[/tex] e dall'operazione prodotto [tex]\cdot[/tex] un gruppo abeliano ogni elemento di tale insieme quoziente ammette inverso.
Le soluzioni possibili sono pertanto le seguenti:
[tex]{\left [1 \right]}_{7} \cdot {\left [ 1\right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [2 \right]}_{7} \cdot {\left [4 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [3 \right]}_{7} \cdot {\left [5 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [4 \right]}_{7} \cdot {\left [2 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [5 \right]}_{7} \cdot {\left [3 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
[tex]{\left [6 \right]}_{7} \cdot {\left [6 \right]}_{7} = {\left [1 \right]}_{7}[/tex]
Grazie mille ancora!!
Controlla i tag, ci sono errori di visualizzazione.
Edit: come non detto
Edit: come non detto
Rettifico: sono riuscito a capire l'ultimo esercizio del primo messaggio, ovvero la soluzione alla [tex]x[/tex] viene dal teorema di Eulero generalizzato perchè la congruenza data è della forma [tex]{\left[ a \right]}^{k \varphi(n)+1}_{n} = {\left[ a \right]}_{n}[/tex] e quindi unica soluzione per [tex]x^5 \equiv {5}_{mod}12[/tex] è [tex]x=5[/tex].
Per il penultimo invece non capisco quale teorema utilizzare, so che se la congruenza fosse lineare le uniche soluzioni ad una congruenza come la seguente [tex]x \equiv 1_{mod}12[/tex] si avrebbero solo per le [tex]4[/tex] classi di equivalenza coprime con [tex]12[/tex], ma come procedo con una congruenza non lineare?
Grazie mille ancora!!
Per il penultimo invece non capisco quale teorema utilizzare, so che se la congruenza fosse lineare le uniche soluzioni ad una congruenza come la seguente [tex]x \equiv 1_{mod}12[/tex] si avrebbero solo per le [tex]4[/tex] classi di equivalenza coprime con [tex]12[/tex], ma come procedo con una congruenza non lineare?
Grazie mille ancora!!
Più che un teorema credo sia sufficiente conoscere la struttura di $(ZZ_n,+,*)$, con $n$ primo o composto, e la funzione di Eulero... Prova a fare un esempio perché potrei anche non aver capito io 
Per una congruenza lineare come [tex]x^6 \equiv {1}_{mod}12[/tex] come procedo? In base a cosa si può dire se ha soluzioni e se non ne ha? Onestamente sono un po' confuso su queste: ho studiato il piccolo teorema di Fermat, il teorema di Eulero ed il teorema di Eulero generalizzato ma non capisco come risolvere questo tipo di congruenze con le potenze, mi puoi dare una guida?
Per quanto riguarda il secondo messaggio, le congruenze da me risolte sono corrette?
Come posso procedere se devo trovare tutti i valori [tex]x<13[/tex] che risolvono [tex]x^{242} \equiv {4}_{mod}12[/tex]? Posso semplicemente dire che le soluzioni sono [tex]\varphi(13)[/tex]? Come lo capisco?
Grazie mille ancora!!
Per quanto riguarda il secondo messaggio, le congruenze da me risolte sono corrette?
Come posso procedere se devo trovare tutti i valori [tex]x<13[/tex] che risolvono [tex]x^{242} \equiv {4}_{mod}12[/tex]? Posso semplicemente dire che le soluzioni sono [tex]\varphi(13)[/tex]? Come lo capisco?
Grazie mille ancora!!
Guarda, sicuramente ci sono altre strade, però se sai che una congruenza algebrica $ax-=b_(mod n)$ ammette soluzione $<=> d|b$ per $AAb in ZZ$ e $d=MCD(a,n)$, e ammette soluzione $<=> (a,n)=1$ credo sia una buona base di partenza, da questo poi ci si ragiona su. Al momento io non ho individuato un unico modo di risoluzione e ho poca esperienza per risponderti in modo preciso e approfondito.
Grazie mille, mi sei stato d'aiuto!! Nel caso posto ancora.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo