\(\displaystyle (\mathbb{Z}/pq\mathbb{Z})^* \) non è ciclico
Buongiorno a tutti, avrei bisogno di un aiuto per risolvere una congruenza.
Siano \(\displaystyle p \), \(\displaystyle q \), primi distinti dispari. Allora \(\displaystyle \left( \mathbb{Z}/pq\mathbb{Z} \right)^* \) non è ciclico.
So che \(\displaystyle |( \mathbb{Z}/pq\mathbb{Z})^* | = \varphi(pq) = \varphi(p) \varphi(q) = (p-1)(q-1) \) e devo mostrare che \(\displaystyle \forall x \in \mathbb{Z} \ \ x^{\frac{(p-1)(q-1)}{2}} \equiv 1 \pmod{pq} \).
Come posso risolverla?
Ho provato a costruirmi il gruppo \(\displaystyle (\mathbb{Z}/15\mathbb{Z})^* \) e ho notato che gli elementi hanno ordine \(\displaystyle 1 \), \(\displaystyle \varphi(p-1) \) e \(\displaystyle \varphi(q-1) \). Inoltre \(\displaystyle p-1 \) e \(\displaystyle q-1 \) sono entrambi pari, quindi \(\displaystyle \frac{(p-1)(q-1)}{2} \in \mathbb{Z} \). Ho pensato che, essendo \(\displaystyle pq \) il prodotto di 2 primi dispari, \(\displaystyle \operatorname{MCD}(p-1, q-1)\geq 2 \), ma non so né come utilizzarlo, né se serve a qualcosa.
Grazie in anticipo
Siano \(\displaystyle p \), \(\displaystyle q \), primi distinti dispari. Allora \(\displaystyle \left( \mathbb{Z}/pq\mathbb{Z} \right)^* \) non è ciclico.
So che \(\displaystyle |( \mathbb{Z}/pq\mathbb{Z})^* | = \varphi(pq) = \varphi(p) \varphi(q) = (p-1)(q-1) \) e devo mostrare che \(\displaystyle \forall x \in \mathbb{Z} \ \ x^{\frac{(p-1)(q-1)}{2}} \equiv 1 \pmod{pq} \).
Come posso risolverla?
Ho provato a costruirmi il gruppo \(\displaystyle (\mathbb{Z}/15\mathbb{Z})^* \) e ho notato che gli elementi hanno ordine \(\displaystyle 1 \), \(\displaystyle \varphi(p-1) \) e \(\displaystyle \varphi(q-1) \). Inoltre \(\displaystyle p-1 \) e \(\displaystyle q-1 \) sono entrambi pari, quindi \(\displaystyle \frac{(p-1)(q-1)}{2} \in \mathbb{Z} \). Ho pensato che, essendo \(\displaystyle pq \) il prodotto di 2 primi dispari, \(\displaystyle \operatorname{MCD}(p-1, q-1)\geq 2 \), ma non so né come utilizzarlo, né se serve a qualcosa.
Grazie in anticipo
Risposte
Conosci il teorema cinese del resto?
Sì, come posso utilizzarlo?
\((\mathbb Z/pq\mathbb Z)^*\) è isomorfo a \((\mathbb Z/p\mathbb Z)^*\times (\mathbb Z/q\mathbb Z)^*\). Se prendi un elemento $(x,y)$ che sta nel secondo gruppo e lo elevi a \((p-1)(q-1)/2\), che succede?
Sinceramente non so. Premetto che negli appunti che sto seguendo, gli isomorfismi sono dopo l'esercizio che ho chiesto qui sul forum e li ho appena iniziati stamattina. Se puoi orientarmi in qualche modo, sarei ben felice di anticipare qualcosa e capirci un po' di più.
So che
\(\displaystyle \begin{matrix} \phi: &(\mathbb{Z}/pq\mathbb{Z})^*&\longrightarrow &(\mathbb{Z}/p\mathbb{Z})^* \times (\mathbb{Z}/q\mathbb{Z})^* \\
&[a]_{pq}&\longmapsto &([a]_p, [a]_q) \end{matrix} \)
è bigettiva.
Quindi \(\displaystyle \left[ x^{\frac{(p-1)(q-1)}{2}} \right]_{pq} \longmapsto \left(\left[ x^{\frac{(p-1)(q-1)}{2}}\right]_{p}, \left[ x^{\frac{(p-1)(q-1)}{2}}\right]_{q}\right) \).
Però nel caso che tu dici è come se dovessi mappare \(\displaystyle ([a]_p, _q) \longmapsto ? \). Come si fa?
Posso soltanto dire che \(\displaystyle \left([x]_p, [y]_q\right)^\frac{(p-1)(q-1)}{2} = \left(\left[ x^\frac{(p-1)(q-1)}{2}\right]_p, \left[y^\frac{(p-1)(q-1)}{2}\right]_q\right) = \left(\left[x^\frac{q-1}{2}\right]_p, \left[y^\frac{p-1}{2}\right]_q\right) \) per il teorema di Eulero. Poi come posso procedere?
So che
\(\displaystyle \begin{matrix} \phi: &(\mathbb{Z}/pq\mathbb{Z})^*&\longrightarrow &(\mathbb{Z}/p\mathbb{Z})^* \times (\mathbb{Z}/q\mathbb{Z})^* \\
&[a]_{pq}&\longmapsto &([a]_p, [a]_q) \end{matrix} \)
è bigettiva.
Quindi \(\displaystyle \left[ x^{\frac{(p-1)(q-1)}{2}} \right]_{pq} \longmapsto \left(\left[ x^{\frac{(p-1)(q-1)}{2}}\right]_{p}, \left[ x^{\frac{(p-1)(q-1)}{2}}\right]_{q}\right) \).
Però nel caso che tu dici è come se dovessi mappare \(\displaystyle ([a]_p, _q) \longmapsto ? \). Come si fa?
Posso soltanto dire che \(\displaystyle \left([x]_p, [y]_q\right)^\frac{(p-1)(q-1)}{2} = \left(\left[ x^\frac{(p-1)(q-1)}{2}\right]_p, \left[y^\frac{(p-1)(q-1)}{2}\right]_q\right) = \left(\left[x^\frac{q-1}{2}\right]_p, \left[y^\frac{p-1}{2}\right]_q\right) \) per il teorema di Eulero. Poi come posso procedere?
Prova ad usare la seguente osservazione: \(x^{(p-1)(q-1)/2}=(x^{p-1})^{(q-1)/2}=(x^{q-1})^{(p-1)/2}\).
Ci ho già provato, ma arrivo a
\(\displaystyle \begin{cases}
x^{\frac{q-1}{2}} \equiv 1 \pmod{p} \\
x^{\frac{p-1}{2}} \equiv 1 \pmod{q}
\end{cases} \)
e non so come andare avanti
\(\displaystyle \begin{cases}
x^{\frac{q-1}{2}} \equiv 1 \pmod{p} \\
x^{\frac{p-1}{2}} \equiv 1 \pmod{q}
\end{cases} \)
e non so come andare avanti
Il punto della questione è che \((\mathbb Z/p\mathbb Z)^*\) ha ordine $p-1$, quindi $x^{p-1}\equiv 1 \mod p$ (a patto che $p$ non divida $x$ ovviamente).
Quindi da \(\displaystyle |(\mathbb{Z}/p\mathbb{Z})^*|=p-1 \) e \(\displaystyle |(\mathbb{Z}/q\mathbb{Z})^*|=q-1 \) e considerando degli elementi \(\displaystyle x \in (\mathbb{Z}/p\mathbb{Z})^*\) e \(\displaystyle y \in (\mathbb{Z}/q\mathbb{Z})^*\) che hanno ordine \(\displaystyle p-1 \) e \(\displaystyle q-1 \) rispettivamente, possiamo dedurre che un elemento \(\displaystyle g = (x, y) \in (\mathbb{Z}/p\mathbb{Z})^* \times (\mathbb{Z}/q\mathbb{Z})^* \) ha ordine \(\displaystyle \operatorname{ord}(g)=\operatorname{mcm}(p-1, q-1) = \frac{(p-1)(q-1)}{\operatorname{MCD}(p-1, q-1)} \leq \frac{(p-1)(q-1)}{2} \) per quanto detto nel primo messaggio. Se non esiste un elemento di ordine \(\displaystyle (p-1)(q-1) \) allora \(\displaystyle (\mathbb{Z}/pq\mathbb{Z})^* \) non è ciclico.
Quindi \(\displaystyle \operatorname{ord}(g) = \frac{\varphi(pq)}{\operatorname{MCD}(\varphi(p), \varphi(q))} \leq \frac{\varphi(pq)}{2} \) e \(\displaystyle 2 \mid \operatorname{MCD}(\varphi(p), \varphi(q)) \), quindi \(\displaystyle \frac{\varphi(pq)}{\operatorname{MCD}(\varphi(p), \varphi(q))} \mid \frac{\varphi(pq)}{2} \) e la congruenza
\( \displaystyle \forall x \in \mathbb{Z} \ \ x^{\frac{\varphi(pq)}{2}} \equiv 1 \pmod{pq} \)
si potrebbe vedere come
\(\displaystyle \left( x^{\frac{\varphi(pq)}{\operatorname{MCD}(\varphi(p), \varphi(q))}} \right)^\frac{\operatorname{MCD}(\varphi(p), \varphi(q))}{2} \equiv 1 \pmod{pq} \) e sarebbe quindi verificata \(\displaystyle \forall x \in \mathbb{Z} \) .
E' corretto il ragionamento?
Quindi \(\displaystyle \operatorname{ord}(g) = \frac{\varphi(pq)}{\operatorname{MCD}(\varphi(p), \varphi(q))} \leq \frac{\varphi(pq)}{2} \) e \(\displaystyle 2 \mid \operatorname{MCD}(\varphi(p), \varphi(q)) \), quindi \(\displaystyle \frac{\varphi(pq)}{\operatorname{MCD}(\varphi(p), \varphi(q))} \mid \frac{\varphi(pq)}{2} \) e la congruenza
\( \displaystyle \forall x \in \mathbb{Z} \ \ x^{\frac{\varphi(pq)}{2}} \equiv 1 \pmod{pq} \)
si potrebbe vedere come
\(\displaystyle \left( x^{\frac{\varphi(pq)}{\operatorname{MCD}(\varphi(p), \varphi(q))}} \right)^\frac{\operatorname{MCD}(\varphi(p), \varphi(q))}{2} \equiv 1 \pmod{pq} \) e sarebbe quindi verificata \(\displaystyle \forall x \in \mathbb{Z} \) .
E' corretto il ragionamento?
Stai complicando tutto senza ragione. Tra l'altro stai anche tralasciando l'ipotesi fondamentale che $(x,pq)=1$. Detto questo, \(x^{(p-1)(q-1)/2}\equiv 1 \mod pq\) se e solo se \(x^{(p-1)(q-1)/2}\equiv 1 \mod p\) E \(x^{(p-1)(q-1)/2}\equiv 1 \mod q\), per il teorema cinese del resto. Ma queste due congruenze sono senz'altro verificate perchè \(x^{(p-1)(q-1)/2}={(x^{p-1})}^{(q-1)/2}\equiv 1^{(q-1)/2}\equiv 1 \mod p\), dal momento che \(|(\mathbb Z/p\mathbb Z)^*|=p-1\), e analogamente per $q$.
Che dire. Era semplice ma non lo vedevo. Inoltre ho notato un errore che facevo che non devo più ricommettere 
L'ipotesi fondamentale $ (x,pq)=1 $ non era negli appunti, ma hai ragione: senza quella la congruenza non sarebbe verificata.
Grazie hydro dell'aiuto e della pazienza.
L'ipotesi fondamentale $ (x,pq)=1 $ non era negli appunti, ma hai ragione: senza quella la congruenza non sarebbe verificata.
Grazie hydro dell'aiuto e della pazienza.
"complesso":
Che dire. Era semplice ma non lo vedevo.
Vai tranquill*, è solo questione di abitudine. Studiando seriamente queste cose diverranno facili!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo