Qualche idea (esempi, più che altro):
1) Consideriamo l'equazione congruenziale (lineare)
[tex]13x \equiv_{7} 3[/tex] (scrittura equivalente a
[tex]13x \equiv 3 \pmod{7}[/tex]; nel caso in cui a te sia nota questa e non quella)
- Possiamo risolvere un'equazione diofantea lineare in due incognite:
[tex]13x \equiv_7 3 \iff (\exists y)(y \in \mathbb{Z} \land 13x = 7y + 3) \iff (\exists y)(y \in \mathbb{Z} \land 13x-7y=3)[/tex]
È quindi sufficiente risolvere l'equazione diofantea lineare
[tex]\boxed{13x-7y = 3}[/tex]
-Possiamo scoprire l'inverso moltiplicativo di [tex]13[/tex] modulo [tex]7[/tex]:
Cos'è?
Banalmente, è quell'intero
[tex]k[/tex] (classe di interi, più precisamente) tale che
[tex]k \cdot 13 \equiv_{7} 1[/tex].
Come trovarlo?
Per tentativi o applicando il
piccolo teorema di Fermat:
[tex]13^6 \equiv_{7} 1[/tex], conseguentemente
[tex]13^5 \cdot 13 \equiv_{7} 1[/tex], quindi
[tex]13^5 \equiv_{7} (-1)^5 \equiv_{7} -1 \equiv_{7} 6[/tex]
è inverso moltiplicativo di
[tex]13[/tex] modulo
[tex]7[/tex].
Dalle ipotesi sull'ammissione di soluzioni di una equazione lineare e da quelle del piccolo teorema di Fermat puoi farti un'idea (precisa) di quelle necessarie affinché un'equazione congruenziale (lineare) abbia soluzione e sull'esistenza dell'inverso moltiplicativo.
2.1) In un certo senso: esattamente come si risolve una equazione congruenziale e come si risolve un sistema di equazioni lineari;
Esempio:
[tex]\begin{equation}
\begin{cases}
13x \equiv_{7} 3\\ 12x \equiv_{5} 1
\end{cases}
\end{equation}[/tex]
Per mezzo di quanto spiegato precedentemente riportiamo questo sistema al sistema
[tex]\begin{equation}
\begin{cases}
x \equiv_{7} 4\\ x \equiv_{5} 3
\end{cases}
\end{equation}[/tex]
La prima è equivalente a
[tex]x = 7k+4[/tex] per qualche
[tex]k \in \mathbb{Z}[/tex], quindi sostituendo nella seconda abbiamo
[tex]7k+4 \equiv_{5} 3 \rightarrow 2k \equiv_{5} 4 \rightarrow k \equiv_{5} 2 \iff k = 5m+2[/tex] per qualche
[tex]m \in \mathbb{Z}[/tex], da cui
[tex]\boxed{x}=7(5m+2)+4=\boxed{35m+18}[/tex], ossia
[tex]\boxed{x \equiv_{35} 18}[/tex].
Questo metodo è generalizzabile a sistemi lineari congruenziali in più di due incognite.
Dai un'occhiata anche al
teorema cinese del resto.
2.2) Teoricamente, come si risolve un'equazione lineare a due incognite.
Sia data l'equazione diofantea lineare in tre incognite
[tex]ax+by+cz=k[/tex] (e supponiamo essa sia risolubile) e sia
[tex]S_k[/tex] l'insieme delle sue soluzioni; sia invece
[tex]S_0[/tex] l'insieme delle soluzioni dell'equazione lineare omogenea
[tex]ax+by+cz=0[/tex].
Scegliamo
[tex](x_1,y_1, z_1) \in S_k[/tex].
Sia
[tex](x_2, y_2, z_2)\in S_k[/tex], allora
[tex](x_1-x_2, y_1-y_2, z_1-z_2) \in S_0[/tex]; viceversa, se
[tex](x_0, y_0, z_0) \in S_0[/tex] allora
[tex](x_1+x_0, y_1+y_0, z_1+z_0) \in S_k[/tex].
Da questo segue, quindi,
[tex]S_k = (x_1, y_1, z_1) + S_0[/tex], ossia tutte le soluzioni della non omogenea si ottengono addizionando una soluzione particolare della non omogenea a ciascuna soluzione della omogenea.
L'argomento può essere facilmente generalizzato ad un numero
[tex]n>3[/tex] di incognite.
Il problema, però, è che generalmente non è facile parametrizzare le soluzioni di
[tex]S_0[/tex], come invece risulta agilmente fattibile in caso di equazioni diofantee lineari a due sole incognite.
Esempio (di risoluzione):
[tex]x+2y+3z = 7[/tex]
Fissiamo
[tex]z=z_0 \in \mathbb{Z}[/tex], allora vogliamo risolvere la diofantea in due incognite
[tex]x+2y = 7-3z_0[/tex].
[tex]x+2y=0[/tex] ha soluzioni
[tex]x=-2k[/tex],
[tex]y=k[/tex] al variare di
[tex]k \in \mathbb{Z}[/tex].
Una soluzione particolare di
[tex]x+2y=7-3z_0[/tex] è
[tex]x' = 1-3z_0, y' = 3[/tex], quindi tutte le soluzioni della diofantea sono della forma
[tex](x,y)=(-2k+1-3z_0, k+3)[/tex].
Per quanto detto, dunque possiamo parametrizzare gli elementi di
[tex]S_7[/tex] come
[tex](-2k_1-3k_2+1, k_1+3, k_2)[/tex] al variare di
[tex]k_1, k_2[/tex] in
[tex]\mathbb{Z}[/tex].
Metodo alternativo per mezzo delle congruenze:
[tex]x+2y = 7-3z_0[/tex], quindi
[tex]x \equiv_{2} 7-z_0 \iff x = 2m_1-z_0+7[/tex] per qualche
[tex]m_1 \in \mathbb{Z}[/tex]; sostituiamo
[tex]2m_1-z_0+7+2y=7-3z_0 \rightarrow y = -m_1-z_0[/tex]; ponendo
[tex]z_0=m_2 \in \mathbb{Z}[/tex] giungiamo alla parametrizzazione
[tex](2m_1-m_2+7, -m_1-m_2, m_2)[/tex]
Esempio: [tex]6z+10y-15z = 1[/tex]
3) Diciamo che
[tex]k \in \mathbb{Z}[/tex] è residuo quadratico modulo
[tex]p[/tex] se e solo se esiste un intero
[tex]m[/tex] tale che
[tex]m^2 \equiv_{p}k[/tex].
Ad esempio, l'insieme dei residui quadratici modulo
[tex]3[/tex] è
[tex]\{0,1\}[/tex], mentre quello modulo
[tex]5[/tex] è
[tex]\{0, 1, 4\}[/tex].
(Nuovamente, il residuo quadratico non è il numero in sé, bensì la classe di resto da esso identificata: come esempio, non è solo
[tex]1[/tex] un residuo quadratico modulo
[tex]3[/tex] ma anche ogni numero della forma
[tex]3h+1[/tex], per ogni
[tex]h \in \mathbb{Z}[/tex])
[Come determinare tali insiemi? Semplice, consideri i naturali da
[tex]0[/tex] fino a
[tex]p-1[/tex], li elevi al quadrato e li riduci modulo
[tex]p[/tex].]
Esempi d'utilizzo [in particolare, risoluzione e dimostrazioni di irrisolubilità di equazioni diofantee non lineari]:
1,
2,
3 (nella sezione
Teoria dei Numeri puoi trovarne altri).
Esempio dalla gara nazionale del 1995: Trovare tutte le coppie di numeri interi positivi
[tex]x, y[/tex] tali che
[tex]x^2+615=2^y[/tex]
4) Domanda eccessivamente generica, più della precedente; risposta particolare:
teorema di eulero - una generalizzazione del piccolo teorema di Fermat.
Con questo potresti risolvere il seguente
problema:
"Definiamo una sequenza
[tex]\{a_i\}_{1 \le n \in \mathbb{N \setminus \{0\}}}[/tex] mediante
[tex]a_1=3[/tex] e
[tex]a_{i+1} = 3^{a_i}[/tex] per
[tex]i > 1[/tex].
Quale intero a due cifre (assumendo che esso possa avere anche
[tex]0[/tex] come cifra delle decine)
[tex]00 \le h \le 99[/tex] appare come ultime due cifre dell'espansione decimale di infiniti
[tex]a_i[/tex]?"
Appendice
Siano
[tex]u, v, w, k, q \in \mathbb{N}[/tex] e sia
[tex]q[/tex] un primo.
Vogliamo trovare un'espressione per
[tex]\phi(w)[/tex], seguiamo questi passi:
- troviamo un'espressione per
[tex]\phi(q)[/tex];
- troviamo un'espressione per
[tex]\phi(q^k)[/tex];
- dimostriamo che
[tex]\phi[/tex] è moltiplicativa:
[tex]\phi(uv)=\phi(u)\phi(v)[/tex]
- esprimiamo
[tex]w[/tex] come prodotto di potenze di primi e troviamo un'espressione per
[tex]\phi(w)[/tex] sfruttando la moltiplicatività.