Esercizio di aritmetica modulare
Sia \(\displaystyle n \in \mathbb{Z} \) un numero pari.
Sia \(\displaystyle m=n^2+1 \). Dimostrare che \(\displaystyle \bar{n} \in \mathbb{Z}^* _m \) (con cui si intende il gruppo moltiplicativo degli elementi invertibili di \(\displaystyle \mathbb{Z}_m \)) ha ordine \(\displaystyle 4 \).
Dimostrare che ogni divisore primo \(\displaystyle q \) di \(\displaystyle n^2+1 \) soddisfa \(\displaystyle q \equiv 1 \mod 4 \).
Per il primo punto ho proceduto così: \(\displaystyle n^2 \equiv 1 \mod m \Leftrightarrow m \equiv 2 \mod m \Leftrightarrow 2 \equiv 0 \mod m \) ma questo implica che \(\displaystyle m=2 \) che è una contraddizione essendo \(\displaystyle m \) dispari.
\(\displaystyle n^3-1 \equiv (n-1)(n^2+n+1) \equiv (n-1)n \equiv n^2-n \) che è \(\displaystyle \equiv 0 \Leftrightarrow n^2 \equiv n \Leftrightarrow n \equiv 1 \).
\(\displaystyle n^4-1 \equiv (n^2-1)(n^2+1) \equiv 0 \).
Per il secondo punto posso dire che \(\displaystyle q \neq 2 \) poiché divide un numero dispari, perciò \(\displaystyle q \), essendo primo, è dispari e di conseguenza ho due casi: \(\displaystyle q \equiv 1,3 \mod 4 \). La mia idea è di escludere il secondo caso.
So che esistono \(\displaystyle k \in \mathbb{Z} \) e \(\displaystyle h \in \mathbb{Z} \) tali che \(\displaystyle kq=4h+1 \) ma non so se è utile. Qualcuno può darmi un consiglio su come iniziare?
Sia \(\displaystyle m=n^2+1 \). Dimostrare che \(\displaystyle \bar{n} \in \mathbb{Z}^* _m \) (con cui si intende il gruppo moltiplicativo degli elementi invertibili di \(\displaystyle \mathbb{Z}_m \)) ha ordine \(\displaystyle 4 \).
Dimostrare che ogni divisore primo \(\displaystyle q \) di \(\displaystyle n^2+1 \) soddisfa \(\displaystyle q \equiv 1 \mod 4 \).
Per il primo punto ho proceduto così: \(\displaystyle n^2 \equiv 1 \mod m \Leftrightarrow m \equiv 2 \mod m \Leftrightarrow 2 \equiv 0 \mod m \) ma questo implica che \(\displaystyle m=2 \) che è una contraddizione essendo \(\displaystyle m \) dispari.
\(\displaystyle n^3-1 \equiv (n-1)(n^2+n+1) \equiv (n-1)n \equiv n^2-n \) che è \(\displaystyle \equiv 0 \Leftrightarrow n^2 \equiv n \Leftrightarrow n \equiv 1 \).
\(\displaystyle n^4-1 \equiv (n^2-1)(n^2+1) \equiv 0 \).
Per il secondo punto posso dire che \(\displaystyle q \neq 2 \) poiché divide un numero dispari, perciò \(\displaystyle q \), essendo primo, è dispari e di conseguenza ho due casi: \(\displaystyle q \equiv 1,3 \mod 4 \). La mia idea è di escludere il secondo caso.
So che esistono \(\displaystyle k \in \mathbb{Z} \) e \(\displaystyle h \in \mathbb{Z} \) tali che \(\displaystyle kq=4h+1 \) ma non so se è utile. Qualcuno può darmi un consiglio su come iniziare?
Risposte
"Antimius":
Per il primo punto ho proceduto così: \(\displaystyle n^2 \equiv 1 \mod m \Leftrightarrow m \equiv 2 \mod m \Leftrightarrow 2 \equiv 0 \mod m \) ma questo implica che \(\displaystyle m=2 \) che è una contraddizione essendo \(\displaystyle m \) dispari.
Qui non ti seguo...
[tex]\displaystyle m=n^2+1 \Rightarrow n^2 \equiv -1 \mod m[/tex]
Procedevo per assurdo. Se fosse \(\displaystyle n^2 \equiv 1 \) si avrebbe \(\displaystyle n^2+1 \equiv 2 \) ossia \(\displaystyle m \equiv 2 \).
Scriviamo \( n^2+1=kq\) con \( n\) pari e \(q\) primo necessariamente dispari.
Seque \( n^2 \equiv -1 \) \( mod\) \( q \)
da cui:
\( (n^2)^{\frac{q-q}{2}} \equiv (-1)^{\frac{q-q}{2}}\)
\( n^{q-1} \equiv (-1)^{\frac{q-1}{2}}\)
Siccome \( q\) non divide \(n\) per il piccolo teorema di Fermat:
\( n^{q-1} \equiv 1 \equiv (-1)^{\frac{q-1}{2}}\)
da cui segue necessariamente che \( \frac{q-1}{2}\) deve essere pari, ossia:
\( \frac{q-1}{2}=2t\), \( q=4t+1\), \(q \equiv 1 \) mod \(q\).
Seque \( n^2 \equiv -1 \) \( mod\) \( q \)
da cui:
\( (n^2)^{\frac{q-q}{2}} \equiv (-1)^{\frac{q-q}{2}}\)
\( n^{q-1} \equiv (-1)^{\frac{q-1}{2}}\)
Siccome \( q\) non divide \(n\) per il piccolo teorema di Fermat:
\( n^{q-1} \equiv 1 \equiv (-1)^{\frac{q-1}{2}}\)
da cui segue necessariamente che \( \frac{q-1}{2}\) deve essere pari, ossia:
\( \frac{q-1}{2}=2t\), \( q=4t+1\), \(q \equiv 1 \) mod \(q\).
Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo