Equazione diofantea
Buongiorno, consideriamo l'equazione 3x+5y+7z+11t=100.
Ho alcune domande.
Argomento equazioni diofantee viene affrontato in qualche liceo o in qualche corso univeristario ?
Vedo su internet post sulla risoluzione con due variabili o anche con 3.
Una equazione di questo tipo come si potrebbe risolvere ?
Come considerate il livello di difficoltà ?
Grazie
OH
Ho alcune domande.
Argomento equazioni diofantee viene affrontato in qualche liceo o in qualche corso univeristario ?
Vedo su internet post sulla risoluzione con due variabili o anche con 3.
Una equazione di questo tipo come si potrebbe risolvere ?
Come considerate il livello di difficoltà ?
Grazie
OH
Risposte
Una sola equazione con 4 incognite ? Non si risolve, non significa nulla. Puoi assegnare infiniti valori a 3 delle 4 incognite, e trovi la quarta , ma non ha alcun senso.
le equazioni diofantee tipo quella che ho scritto oppure 3x+5y+11z=32 sono equazioni per le quali si cercano soluzioni intere.
Se scrivo 5x+11y=15 trovare le soluzioni intere (numeri relativi è semplice (ma non come tu hai indicato).
Forse dovresti documentarti un po' sulle equazioni diofantee..
ciao
OH
Se scrivo 5x+11y=15 trovare le soluzioni intere (numeri relativi è semplice (ma non come tu hai indicato).
Forse dovresti documentarti un po' sulle equazioni diofantee..
ciao
OH
Ah si , hai ragione, diofantee... non ho fatto molto caso. No , non so dirti nulla.
In generale, se una equazione diofantea ha soluzioni, queste sono infinite se non ci sono altri vincoli.
Non ho idea se esistono metodi risolutivi diretti per risolvere equazioni diofantee per ogni valore di $n$ incognite; comunque si può sempre fare come gli antichi cioè ragionandoci su
Per esempio …
Cordialmente, Alex
Non ho idea se esistono metodi risolutivi diretti per risolvere equazioni diofantee per ogni valore di $n$ incognite; comunque si può sempre fare come gli antichi cioè ragionandoci su
Per esempio …
Cordialmente, Alex
niente di male, mi offri l'occasione per un esempio. Si deve trasportare un container con esattamente 400 kg di oro. Si hanno lingotti da 3,5,7,11 kg ciascuno. Come devono essere scelti i lingotti sapendo che bisogna utilizzare i 4 tipi ?
Abbiamo l'equazione 3x+5y+7z+11t=400.
La soluzione è
x=-1600+20a+13b+2c
y=800-9a-6b-2c
z=800-10a-6b-c
t=-400+5a+3b+c
per a=50, b=48, c=10 abbiamo la soluzione x=44, y=42, z=2, t=4. Si possono cercare altre soluzioni modificando i parametri.
ciao
OH
Abbiamo l'equazione 3x+5y+7z+11t=400.
La soluzione è
x=-1600+20a+13b+2c
y=800-9a-6b-2c
z=800-10a-6b-c
t=-400+5a+3b+c
per a=50, b=48, c=10 abbiamo la soluzione x=44, y=42, z=2, t=4. Si possono cercare altre soluzioni modificando i parametri.
ciao
OH
Ciao, ti posso rispondere da quello che mi ricordo dell'argomento ad algebra lineare, sicuramente però non è argomento del liceo.
Sia \( A \in \mathbb{Z}^{m \times n} \) e \(b \in \mathbb{Z}^m \) vogliamo cercare le soluzioni con \(x \in \mathbb{Z}^n \) al problema seguente
\[ Ax = b \]
Per fare ciò dobbiamo spostarci su un problema più semplice, ovvero trovare una matrice unimodulare \(U \), ovvero una matrice \( U \in \mathbb{Z}^{n \times n} \) tale che \( \det(U) = \pm 1 \), tale che \( AU = [H \mid 0 ] \) dove \( H \) è in forma normale di Hermite, o più semplicemente \(H \in \mathbb{Z}^{m \times m} \) ed è triangolare inferiore.
Abbiamo che il problema iniziale \( Ax = b\) possiede soluzioni se e solo se \(H^{-1} b \in \mathbb{Z}^n \), inoltre \( y\) è soluzione del problema \( AUy=b \) se e solo se \(x=Uy \) è soluzione del problema \( Ax =b \). Generalmente il problema \(AUy=b \) è semplice da risolvere.
Nel tuo caso
\[ A= \begin{pmatrix}
3 & 5 & 7 & 11
\end{pmatrix} \] e dove \(b = (100) \)
Per trovare la matrice unimodulare \(U \) richiesta effettuiamo una successione \(U_1,\ldots,U_k\) di operazioni elementari unimodulari su \(A\), ovvero
i) Moltiplicare una colonna di \(A\) per -1
ii) Scambiare due colonne di \(A\)
iii) Addizionare un multiplo intero di una colonna di \(A\) su un'altra colonna di \(A\).
Ed otteniamo \(U=U_1 \cdot \ldots \cdot U_k \)
Nel tuo esempio iniziale abbiamo che la successione di operazioni elementari è data da
\[ U_1 =\begin{pmatrix}
1&0&0&0\\
0&1&-1&0\\
0&0&1&0\\
0&0&0&1
\end{pmatrix}\]
\[ U_2 =\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
-1&0&1&0\\
0&0&0&1
\end{pmatrix}\]
\[ U_3 =\begin{pmatrix}
1&-5&-2&-11\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1
\end{pmatrix}\]
otteniamo dunque \[ U= U_1 \cdot U_2 \cdot U_3 =\begin{pmatrix}
1&-5&-2&-11\\
1&-4&-3&-11\\
-1&5&3&11\\
0&0&0&1
\end{pmatrix}\]
Ora invece di risolvere il problema \(Ax = (100) \) risolviamo
\[ A U y = \begin{pmatrix}
1 & 0 & 0 & 0
\end{pmatrix} y = (100) \]
questo problema è decisamente più facile da risolvere ed otteniamo come soluzione
\[ y =
\begin{pmatrix}
100\\
0\\
0\\
0
\end{pmatrix}\]
Ora per trovare una soluzione al problema iniziale calcoliamo
\[ x =Uy = \begin{pmatrix}
1&-5&-2&-11\\
1&-4&-3&-11\\
-1&5&3&11\\
0&0&0&1
\end{pmatrix}\begin{pmatrix}
100\\
0\\
0\\
0
\end{pmatrix}=\begin{pmatrix}
100\\
100\\
-100\\
0
\end{pmatrix}\]
Per trovare l'insieme delle soluzioni totali notiamo che le colonne 2,3,4 della matrice \(U \) mandano \(A \) a zero. Dunque ciascuna soluzione del problema è scrivibile nel seguente modo
\[
\begin{pmatrix}
100\\
100\\
-100\\
0
\end{pmatrix} + \alpha \cdot \begin{pmatrix}
-5\\
-4\\
5\\
0
\end{pmatrix} +\beta \cdot \begin{pmatrix}
-2\\
-3\\
3\\
0
\end{pmatrix} +\gamma \cdot \begin{pmatrix}
-11\\
-11\\
11\\
1
\end{pmatrix} \]
con \(\alpha, \beta, \gamma \in \mathbb{Z} \).
Edit
In questo modo puoi risolvere pure sistemi. Ad esempio
\[ \begin{pmatrix}
4& 6 &10 \\
6& 12 &9
\end{pmatrix}\begin{pmatrix}
x\\
y\\
z
\end{pmatrix} = \begin{pmatrix}
6\\
3
\end{pmatrix} \]
ha come insieme di soluzione
\[ \begin{Bmatrix} \begin{pmatrix}
-23\\
8\\
5
\end{pmatrix} + \alpha\begin{pmatrix}
11\\
-4\\
-2
\end{pmatrix} : \alpha \in \mathbb{Z}
\end{Bmatrix}\]
E la matrice unimodulare \( U \) è data da
\[ U =\begin{pmatrix}
-9&4&11\\
3&-1&-4\\
2&-1&-2
\end{pmatrix}\]
Sia \( A \in \mathbb{Z}^{m \times n} \) e \(b \in \mathbb{Z}^m \) vogliamo cercare le soluzioni con \(x \in \mathbb{Z}^n \) al problema seguente
\[ Ax = b \]
Per fare ciò dobbiamo spostarci su un problema più semplice, ovvero trovare una matrice unimodulare \(U \), ovvero una matrice \( U \in \mathbb{Z}^{n \times n} \) tale che \( \det(U) = \pm 1 \), tale che \( AU = [H \mid 0 ] \) dove \( H \) è in forma normale di Hermite, o più semplicemente \(H \in \mathbb{Z}^{m \times m} \) ed è triangolare inferiore.
Abbiamo che il problema iniziale \( Ax = b\) possiede soluzioni se e solo se \(H^{-1} b \in \mathbb{Z}^n \), inoltre \( y\) è soluzione del problema \( AUy=b \) se e solo se \(x=Uy \) è soluzione del problema \( Ax =b \). Generalmente il problema \(AUy=b \) è semplice da risolvere.
Nel tuo caso
\[ A= \begin{pmatrix}
3 & 5 & 7 & 11
\end{pmatrix} \] e dove \(b = (100) \)
Per trovare la matrice unimodulare \(U \) richiesta effettuiamo una successione \(U_1,\ldots,U_k\) di operazioni elementari unimodulari su \(A\), ovvero
i) Moltiplicare una colonna di \(A\) per -1
ii) Scambiare due colonne di \(A\)
iii) Addizionare un multiplo intero di una colonna di \(A\) su un'altra colonna di \(A\).
Ed otteniamo \(U=U_1 \cdot \ldots \cdot U_k \)
Nel tuo esempio iniziale abbiamo che la successione di operazioni elementari è data da
\[ U_1 =\begin{pmatrix}
1&0&0&0\\
0&1&-1&0\\
0&0&1&0\\
0&0&0&1
\end{pmatrix}\]
\[ U_2 =\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
-1&0&1&0\\
0&0&0&1
\end{pmatrix}\]
\[ U_3 =\begin{pmatrix}
1&-5&-2&-11\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1
\end{pmatrix}\]
otteniamo dunque \[ U= U_1 \cdot U_2 \cdot U_3 =\begin{pmatrix}
1&-5&-2&-11\\
1&-4&-3&-11\\
-1&5&3&11\\
0&0&0&1
\end{pmatrix}\]
Ora invece di risolvere il problema \(Ax = (100) \) risolviamo
\[ A U y = \begin{pmatrix}
1 & 0 & 0 & 0
\end{pmatrix} y = (100) \]
questo problema è decisamente più facile da risolvere ed otteniamo come soluzione
\[ y =
\begin{pmatrix}
100\\
0\\
0\\
0
\end{pmatrix}\]
Ora per trovare una soluzione al problema iniziale calcoliamo
\[ x =Uy = \begin{pmatrix}
1&-5&-2&-11\\
1&-4&-3&-11\\
-1&5&3&11\\
0&0&0&1
\end{pmatrix}\begin{pmatrix}
100\\
0\\
0\\
0
\end{pmatrix}=\begin{pmatrix}
100\\
100\\
-100\\
0
\end{pmatrix}\]
Per trovare l'insieme delle soluzioni totali notiamo che le colonne 2,3,4 della matrice \(U \) mandano \(A \) a zero. Dunque ciascuna soluzione del problema è scrivibile nel seguente modo
\[
\begin{pmatrix}
100\\
100\\
-100\\
0
\end{pmatrix} + \alpha \cdot \begin{pmatrix}
-5\\
-4\\
5\\
0
\end{pmatrix} +\beta \cdot \begin{pmatrix}
-2\\
-3\\
3\\
0
\end{pmatrix} +\gamma \cdot \begin{pmatrix}
-11\\
-11\\
11\\
1
\end{pmatrix} \]
con \(\alpha, \beta, \gamma \in \mathbb{Z} \).
Edit
In questo modo puoi risolvere pure sistemi. Ad esempio
\[ \begin{pmatrix}
4& 6 &10 \\
6& 12 &9
\end{pmatrix}\begin{pmatrix}
x\\
y\\
z
\end{pmatrix} = \begin{pmatrix}
6\\
3
\end{pmatrix} \]
ha come insieme di soluzione
\[ \begin{Bmatrix} \begin{pmatrix}
-23\\
8\\
5
\end{pmatrix} + \alpha\begin{pmatrix}
11\\
-4\\
-2
\end{pmatrix} : \alpha \in \mathbb{Z}
\end{Bmatrix}\]
E la matrice unimodulare \( U \) è data da
\[ U =\begin{pmatrix}
-9&4&11\\
3&-1&-4\\
2&-1&-2
\end{pmatrix}\]
Come avrai capito non è un argomento che viene affrontato di solito alla scuola di secondo grado. Ricordo un unico libro di una ventina di anni fa che lasciava un paio di pagine alle equazioni diofantee. Io lo sposterei in Algebra.
La struttura generale delle soluzione di un'equazione diofantea è, come nel caso "lineare" a coefficienti in un campo, e con la "stessa" dimostrazione (salvo che i coefficienti son presi in un anello e non in campo):
soluzione particolare più nucleo (o "sizigie"),
perché la risoluzione di una tale equazione corrisponde a calcolare la fibra (=controimmagine) di una applicazione $\mathbb Z$-lineare da un qualche $\mathbb Z^k$ verso $\mathbb Z$. Un possibile quadro teorico è la teoria dei moduli finitamente generati su un dominio a ideali principali (PID), in particolare gli $\mathbb Z$-moduli, e la cosiddetta "forma normale di Smith" (Smith normal form), non ho controllato se i conti di 3m0o corrispondono a quelli dell'algoritmo classico, ma l'idea è quella:
https://core.ac.uk/download/pdf/82343294.pdf
https://en.wikipedia.org/wiki/Smith_normal_form
Nei casi più semplici, le equazioni diofantee possono essere risolte abbastanza semplicemente, a mano, usando l'algoritmo euclideo per il calcolo del MCD.
Esempi
(1) $6x-21y=58$: non ha soluzioni intere perché 58 non è divisibile per 3;
(2) $6x-21y=57$: ora $57=3*19$ è divisibile per 3 e MCD(6;21)=3 perché,
per il teorema di Bezout: https://it.wikipedia.org/wiki/Identit%C ... %C3%A9zout)
$6*4-21*1=3$,
quindi una soluzione particolare dell'equazione è data dalla coppia $v:=(4*19;1*19)$, mentre il nucleo dell'applicazione "lineare" $f(x;y):=6x-21y$ si trova risolvendo, in $\mathbb Z^2$, l'equazione $6x-21y=0\iff 2x=7y$, ma poiché $2$ e $7$ sono primi tra loro e $x$ e $y$ sono interi, deve essere $x=7h$ e $y=2h$ per qualche (lo stesso...) intero $h$. Le soluzioni intere dell'equazione $6x-21y=57$ sono quindi tutte e sole quelle della forma
$(x;y)=v+\ker f=(76; 19)+h(7; 2)=(76+7h; 19+2h)$ al variare di $h$, arbitrariamente, negli interi.
Il caso con più di due incognite, salvo casi banali, si tratta meglio, come ti ha mostrato 3m0o, col formalismo delle matrici.
Non mi sembra sia un argomento da liceo, se non per qualche approfondimento/gara/eccellenza...
soluzione particolare più nucleo (o "sizigie"),
perché la risoluzione di una tale equazione corrisponde a calcolare la fibra (=controimmagine) di una applicazione $\mathbb Z$-lineare da un qualche $\mathbb Z^k$ verso $\mathbb Z$. Un possibile quadro teorico è la teoria dei moduli finitamente generati su un dominio a ideali principali (PID), in particolare gli $\mathbb Z$-moduli, e la cosiddetta "forma normale di Smith" (Smith normal form), non ho controllato se i conti di 3m0o corrispondono a quelli dell'algoritmo classico, ma l'idea è quella:
https://core.ac.uk/download/pdf/82343294.pdf
https://en.wikipedia.org/wiki/Smith_normal_form
Nei casi più semplici, le equazioni diofantee possono essere risolte abbastanza semplicemente, a mano, usando l'algoritmo euclideo per il calcolo del MCD.
Esempi
(1) $6x-21y=58$: non ha soluzioni intere perché 58 non è divisibile per 3;
(2) $6x-21y=57$: ora $57=3*19$ è divisibile per 3 e MCD(6;21)=3 perché,
per il teorema di Bezout: https://it.wikipedia.org/wiki/Identit%C ... %C3%A9zout)
$6*4-21*1=3$,
quindi una soluzione particolare dell'equazione è data dalla coppia $v:=(4*19;1*19)$, mentre il nucleo dell'applicazione "lineare" $f(x;y):=6x-21y$ si trova risolvendo, in $\mathbb Z^2$, l'equazione $6x-21y=0\iff 2x=7y$, ma poiché $2$ e $7$ sono primi tra loro e $x$ e $y$ sono interi, deve essere $x=7h$ e $y=2h$ per qualche (lo stesso...) intero $h$. Le soluzioni intere dell'equazione $6x-21y=57$ sono quindi tutte e sole quelle della forma
$(x;y)=v+\ker f=(76; 19)+h(7; 2)=(76+7h; 19+2h)$ al variare di $h$, arbitrariamente, negli interi.
Il caso con più di due incognite, salvo casi banali, si tratta meglio, come ti ha mostrato 3m0o, col formalismo delle matrici.
Non mi sembra sia un argomento da liceo, se non per qualche approfondimento/gara/eccellenza...
"@melia":
Come avrai capito non è un argomento che viene affrontato di solito alla scuola di secondo grado. Ricordo un unico libro di una ventina di anni fa che lasciava un paio di pagine alle equazioni diofantee. Io lo sposterei in Algebra.
Ciao @melia, posso chiederti, se lo ricordi, che libro era? forse un testo per il PNI? Grazie, un saluto
"alessio76":
La struttura generale delle soluzione di un'equazione diofantea è, come nel caso "lineare" a coefficienti in un campo, e con la "stessa" dimostrazione (salvo che i coefficienti son presi in un anello e non in campo):
soluzione particolare più nucleo (o "sizigie"),
Non mi sembra sia un argomento da liceo, se non per qualche approfondimento/gara/eccellenza...
ti ringrazio molto: io ho risolto l'equazione in 6 variabili (facile controlare che la soluzione è giusta) con un mio metodo basato su considerazioni elementari, a livello di 1 liceo. Mi piacerebbe molto vedere la soluzione con il metodo che hai esposto. é dagli esempi che si può imparare molto. Grazie.
ciao
Oliver
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo