Lacune di TDN

Tutto ciò che dovete sapere per arrivare preparati alle competizioni matematiche.
Rispondi
Buraka
Messaggi: 7
Iscritto il: 02/04/2018, 16:20

Lacune di TDN

Messaggio da Buraka »

Ho diverse lacune sulla teoria dei numeri che vi elencherò. Vi ringrazio in anticipo delle eventuali risposte.
1) Come si risolve un'equazione modulare? Ho sentito parlare di inverso moltiplicativo...
2.1) Come si risolve un sistema di congruenze? A due equazioni posso usufruire di una diofantea lineare ma a più equazioni?
2.2) Se i sistemi di congruenze si risolvono tutti alla stessa maniera allora la 2.1 implicherebbe questa domanda: "Come si risolvono le diofantee a più incognite"?
3) Cosa sono e come/dove si usano i residui quadratici?
4) Dove si applica la Phi di Eulero?
Ho bisogno di un approccio semplice e veloce in grado di farmi capire senza troppi giri di parole e magari con qualche esempio questi concetti. Ringrazio tutti quelli che scriveranno qui sul topic o mi linkeranno pdf abbastanza comprensibili. Grazie ;)
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Lacune di TDN

Messaggio da afullo »

Inizia provando a buttare un occhio alle Dispense Olimpioniche, che possono già darti delle risposte, poi quando tornerò dalle vacanze sarò più specifico. :)
Buraka
Messaggi: 7
Iscritto il: 02/04/2018, 16:20

Re: Lacune di TDN

Messaggio da Buraka »

Ti ringrazio in anticipo. Il problema è proprio questo... Sto leggendo le dispense olimpioniche e per quanto possano essere fatte bene (Ringrazio chi le ha scritte) alcune cose non riesco a comprenderle/applicarle. :cry:
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Lacune di TDN

Messaggio da Gizeta »

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à.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Lacune di TDN

Messaggio da afullo »

Direi che la risposta di Gizeta sia abbastanza esauriente :mrgreen:

Aggiungerei magari un richiamo all'identità di Bezout per la risoluzione delle equazioni diofantee lineari in due variabili, che si basa sul celebre algoritmo di Euclide. ;)
Buraka
Messaggi: 7
Iscritto il: 02/04/2018, 16:20

Re: Lacune di TDN

Messaggio da Buraka »

Grazie delle risposte. Però ho usato lo stesso metodo per risolvere [tex]3x \equiv 1 (\mathrm{mod} 5)[/tex] ottenendo così [tex]x=\frac{1+5k}{3}[/tex] ma il risultato è invece [tex]x=2+5k[/tex]. Come mai? :oops:
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Lacune di TDN

Messaggio da Gizeta »

Con il primo metodo abbiamo (1) [tex]3x-5y=1[/tex] di cui una soluzione particolare è [tex](x', y')=(2, 1)[/tex], mentre è possibile parametrizzare le soluzioni di [tex]3x-5y=0[/tex] come [tex](x,y)=(5k, 3k)[/tex] con [tex]k \in\mathbb{Z}[/tex], quindi tutte le soluzioni della diofantea (1) sono della forma [tex](5k+2, 3k+1)[/tex], e [tex]\boxed{x=5k+2}\iff \boxed{x \equiv_{5} 2}[/tex]

Con il secondo metodo, invece, abbiamo [tex]3^{5-1} \equiv_{5} 1[/tex] per il piccolo teorema di Fermat, conseguentemente [tex]3^3=27 \equiv_{5} 2[/tex] è inverso moltiplicativo di [tex]3[/tex] modulo [tex]5[/tex], da cui (moltiplicando per [tex]2[/tex] entrambi i membri dell'equazione congruenziale) [tex]2 \cdot 3x \equiv_{5} 2 \cdot 1 \rightarrow \boxed{x \equiv_{5} 2}[/tex]





L'equivalenza dei due metodi ci porta ad una riflessione: siano [tex]a,b,c \in \mathbb{N^{+}}[/tex] e sia data l'equazione diofantea lineare [tex]ax+by=c[/tex]; senza perdita di generalità [tex](a, b)=1[/tex] (in caso contrario si avrebbe anche [tex](a, b) \mid c[/tex], e quindi sarebbe possibile semplificare [tex](a, b)[/tex] ad ambo i membri e ricondursi ad un'equazione del tipo [tex]a'x+b'y=c'[/tex] con [tex](a', b')=1[/tex]).

Con qualche manipolazione ci riconduciamo all'equazione [tex]\displaystyle x=\frac{c-by}{a}[/tex], per cui, dato che [tex]x \in \mathbb{Z}[/tex] per ipotesi, deve valere [tex]c-by \equiv_{a} 0 \rightarrow by \equiv_{a} c[/tex] e moltiplicando per [tex]b^{\phi(a)-1}[/tex] ad entrambi i membri [tex]b^{\phi(a)-1}by =b^{\phi(a)}y \equiv_{a} b^{\phi(a)-1}c[/tex], quindi per il teorema di Eulero [tex]y \equiv_{a} b^{\phi(a)-1}c \iff y = ak+b^{\phi(a)-1}c[/tex] con [tex]k \in \mathbb{Z}[/tex].

Sostituisco e ottengo [tex]\displaystyle x=\frac{c-b(ak+b^{\phi(a)-1}c)}{a}=\frac{-bak-c(b^{\phi(a)}-1)}{a} \rightarrow x=-\frac{c(b^{\phi(a)}-1)}{a}-bk[/tex]

Tutte le soluzioni della diofantea [tex]ax+by=c[/tex] sono quindi della forma [tex]\displaystyle (x,y)=\left(-\frac{c(b^{\phi(a)}-1)}{a}-bk, b^{\phi(a)-1}c+ak \right)[/tex] al variare di [tex]k[/tex] in [tex]\mathbb{Z}[/tex]





A questo punto è banale risolvere anche una diofantea lineare in due incognite a coefficienti negativi.
Ad esempio [tex]ax+by=c[/tex] ([tex]a,c \in \mathbb{N^{+}}[/tex] e [tex]b<0[/tex]), allora possiamo considerare la forma equivalente [tex]ax+|b|(-y)=c[/tex], che sappiamo risolvere con il metodo precedente.
Ultima modifica di Gizeta il 24/08/2018, 8:11, modificato 2 volte in totale.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Lacune di TDN

Messaggio da afullo »

Buraka ha scritto:Grazie delle risposte. Però ho usato lo stesso metodo per risolvere [tex]3x \equiv 1 (\mathrm{mod} 5)[/tex] ottenendo così [tex]x=\frac{1+5k}{3}[/tex] ma il risultato è invece [tex]x=2+5k[/tex]. Come mai? :oops:
Peraltro puoi notare che il risultato che hai ottenuto tu, se intersecato con [tex]\mathbb{Z}[/tex], porta proprio al risultato esatto. Una delle cose a cui fare attenzione è evitare di introdurre soluzioni estranee all'insieme degli interi, ed è questo il motivo per cui bisogna utilizzare tecniche specifiche al posto di quelle tradizionali dell'algebra razionale e reale.
Buraka
Messaggi: 7
Iscritto il: 02/04/2018, 16:20

Re: Lacune di TDN

Messaggio da Buraka »

Ringrazio nuovamente. L'uso delle diofantee per risolvere queste equazioni "modulari" mi è molto più semplice. Proverò ad adattarmi a questo nuovo modo di operare. Per il resto se dovessi avere qualche altro problema scrivo qui. Grazie. :)
Rispondi