Esercizi vari su rel di equivalenza e congruenze
Salve a tutti. Volevo proporvi qualche esercizio che non riesco a portare a termine.
Il primo è questo:
Su $ A=ZZ /(nZZ) $ ($n>1$) definisco la relazione $§$ ponendo $ AA a,b in A $ , $a § b $ se $(a-b)(a+b-1)=nZZ$.
(i) Mostrare che $§$ è una relazione d'ordine. (Svolto senza problemi).
(ii) Determinare la cardinalità dell'insieme $A$ modulo $§$ fissato $n$ numero primo dispari. In questo non riesco bene a capire da che parte devo farmi. La relazione impone che se a e b sono in relazione, $a^2-a-b^2+a$ debba essere un multiplo di $n$ ma ciò non mi aiuta a trovare i rappresentanti delle classi di equivalenza. Suggerimenti?
Il secondo è questo:
Determinare le soluzioni intere di
$x^201-=x^21 (mod 209)$. L'idea è quella di ricondursi al teorema di Fermat ma 209 non è un numero primo. Suggerimenti? Grazie e scusate le domande probabilmente banali.
Il primo è questo:
Su $ A=ZZ /(nZZ) $ ($n>1$) definisco la relazione $§$ ponendo $ AA a,b in A $ , $a § b $ se $(a-b)(a+b-1)=nZZ$.
(i) Mostrare che $§$ è una relazione d'ordine. (Svolto senza problemi).
(ii) Determinare la cardinalità dell'insieme $A$ modulo $§$ fissato $n$ numero primo dispari. In questo non riesco bene a capire da che parte devo farmi. La relazione impone che se a e b sono in relazione, $a^2-a-b^2+a$ debba essere un multiplo di $n$ ma ciò non mi aiuta a trovare i rappresentanti delle classi di equivalenza. Suggerimenti?
Il secondo è questo:
Determinare le soluzioni intere di
$x^201-=x^21 (mod 209)$. L'idea è quella di ricondursi al teorema di Fermat ma 209 non è un numero primo. Suggerimenti? Grazie e scusate le domande probabilmente banali.
Risposte
Per il secondo: [tex]x^{\varphi(n)} \equiv 1 \pmod{n}[/tex] per ogni [tex]x[/tex] coprimo con [tex]n[/tex]. Si chiama teorema di Eulero (credo, ma è una banale conseguenza del teorema di Lagrange per i gruppi). Ora, se tu non hai mai visto questo teorema dimostrato a lezione / non vuoi studiarne la dimostrazione / non ti senti legittimato ad utilizzarlo, non so cosa dire. Magari si può fare qualche giochino e con un po' di fatica far tornare tutto, ma, al momento, non ci ho pensato.
Scusa maurer, non riesco a capire. Ok sulla formula \(x^{\phi(n)}=1\mod n\): per forza, visto che l'ordine di \(x\) in \(\mathbb{Z}/n\mathbb{Z}^\star\) deve dividere \(\phi(n)\). E poi, che fai?
Ok, forse sono stato un po' criptico... Beh [tex]\varphi(209) = \varphi(19) \cdot \varphi(11) = 180[/tex], quindi [tex]x^{201} \equiv x^{21} \pmod{209} \iff x^{201} - x^{21} \equiv 0 \pmod{209} \iff x^{21}(x^{180} - 1) \equiv 0 \pmod{209}[/tex] e quest'ultima è sempre verificata se [tex]x[/tex] è invertibile modulo [tex]209[/tex]. Se invece [tex]x[/tex] non è invertibile modulo [tex]209[/tex] allora [tex]\text{gcd}(x,209) \ne 1[/tex], ossia [tex]11 \mid x[/tex] oppure [tex]19 \mid x[/tex]. Ora, supponiamo ad esempio [tex]11 \mid x[/tex]; chiaramente se [tex]19 \mid x[/tex] allora [tex]x \equiv 0 \pmod{209}[/tex], quindi possiamo supporre [tex]x \not \equiv 0 \pmod{19}[/tex], sicché [tex]x^{180} - 1 = (x^{10})^{\varphi(19)} - 1 \equiv 0 \pmod{19}[/tex] e pertanto [tex]19 \mid x^{180} - 1[/tex], col risultato che [tex]209 \mid x^{21} (x^{180} - 1)[/tex].
Se invece partiamo da [tex]19 \mid x[/tex] allora possiamo supporre come prima [tex]x \not \equiv 0 \pmod{11}[/tex], sicché [tex]x^{180} - 1 = (x^{18})^{\varphi{11}} - 1 \equiv 0 \pmod{11}[/tex] e pertanto [tex]11 \mid x^{180} - 1[/tex], da cui [tex]209 \mid x^{21}(x^{180} - 1)[/tex], da cui finalmente segue che l'equazione di partenza è soddisfatta per ogni valore di [tex]x[/tex].
Se invece partiamo da [tex]19 \mid x[/tex] allora possiamo supporre come prima [tex]x \not \equiv 0 \pmod{11}[/tex], sicché [tex]x^{180} - 1 = (x^{18})^{\varphi{11}} - 1 \equiv 0 \pmod{11}[/tex] e pertanto [tex]11 \mid x^{180} - 1[/tex], da cui [tex]209 \mid x^{21}(x^{180} - 1)[/tex], da cui finalmente segue che l'equazione di partenza è soddisfatta per ogni valore di [tex]x[/tex].
Vi faccio notare che la cosa è vera se al posto di [tex]209[/tex] ci mettiamo un qualsiasi prodotto di due primi distinti [tex]n = pq[/tex] e poi consideriamo [tex]x^{\varphi(n) + k} \equiv x^k \pmod{n}[/tex] con [tex]k < \varphi(n)[/tex].
Mai visto quel teorema effettivamente... Forse ho solamente preso un esercizio non alla mia portata. Grazie comunque 
Per il secondo?
Per il secondo?
Per il primo, vorrai dire. Abbiamo la condizione [tex](a-b)(a+b-1) \equiv 0 \pmod{p}[/tex] con [tex]p[/tex] primo dispari. Per [tex]p[/tex] primo, [tex]\mathbb Z / p \mathbb Z[/tex] è un campo, quindi vale la legge di annullamento del prodotto. In particolare ottieni un sistema di congruenze:
[tex]\begin{cases} a \equiv b \pmod{p} \\ a + b \equiv 1 \pmod{p} \end{cases}[/tex]
Ottieni, in effetti:
[tex]\begin{cases} a \equiv b \pmod{p} \\ b \equiv 2^{-1} \pmod{p} \end{cases} \Rightarrow \begin{cases} a \equiv 2^{-1} \pmod{p}\\ b \equiv 2^{-1} \pmod{p} \end{cases}[/tex]
A questo punto basta calcolare l'inverso di 2 modulo p. Si può fare in assoluta generalità. Ne sei capace?
[tex]\begin{cases} a \equiv b \pmod{p} \\ a + b \equiv 1 \pmod{p} \end{cases}[/tex]
Ottieni, in effetti:
[tex]\begin{cases} a \equiv b \pmod{p} \\ b \equiv 2^{-1} \pmod{p} \end{cases} \Rightarrow \begin{cases} a \equiv 2^{-1} \pmod{p}\\ b \equiv 2^{-1} \pmod{p} \end{cases}[/tex]
A questo punto basta calcolare l'inverso di 2 modulo p. Si può fare in assoluta generalità. Ne sei capace?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo