Questo problema mi ha un po' divertito
Determinare le coppie di interi positivi a e b, assumendo a < b, per le quali, chiamato x il minimo comune multiplo di a e b e y è il loro massimo comune divisore, si ha 2·x - 31·y = 39.
Una diofantea fra il mcm e il MCD.
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Una diofantea fra il mcm e il MCD.
(Bruno)
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
Re: Una diofantea fra il mcm e il MCD.
Caro e ottimo Bruno, mi permetto una piccola variazione di nomenclatura perché $a$ e $b$ mi servono per generalizzare l'equazione. Siano dunque $x=\text{mcm}\left(p,q\right)$ e $y=\text{MCD}\left(p,q\right)$.
L'equazione $a\,x-b\,y=c$ ammette soluzioni intere se e solo $\text{MCD}\left(a,b\right)$ divide $c$. D'altra parte, nessuno scriverebbe mai l'equazione $15x-6y=9$: tutti la semplificherebbero immediatamente a $5x-2y=3$.
Consideriamo sunque solo equazioni per le quali $\text{MCD}\left(a,b\right)=1$, come del resto è nel nostro caso specifico.
Se l'equazione $a\,x-b\,y=c$ ammette soluzioni in $\mathbb{Z}^2$ allora ne ammette infinite. Se $\left(x_0,y_0\right)$ e $\left(x,y\right)$ sono due soluzioni della nostra equazione allora abbiamo che $a\,x_0-b\,y_0=a\,x-b\,y$: rimaneggiamo questa espressione per ottenere
$\displaystyle x-x_0=\frac{b\left(y-y_0\right)}a$
Dato che $x-x_0$ è un intero e che $a$ non divide $b$ allora $a$ deve dividere $\left(y-y_0\right)$. Con un ragionamento analogo troviamo che $b$ deve dividere $\left(x-x_0\right)$.
La soluzione generale della nostra equazione è quindi
$\displaystyle \left\{\begin{array}{lC} x=x_0+n\,b\\y=y_0+n\,a \end{array}\right.$
Alla nostra equazione corrisponde un'equazione "ridotta", $a\,x-b\,y=1$. Sia $\left(x_0^\prime,y_0^\prime\right)$ una soluzione particolare dell'equazione ridotta, ovvero
$\displaystyle a\,x_0^\prime-b\,y_0^\prime=1$
moltiplicando a destra e a sinistra per $c$, otteniamo
$\displaystyle a\,c\,x_0^\prime-b\,c\,y_0^\prime=a\,x_0-b\,y_0=c$
cioè, $\left(x_0,y_0\right)=\left(c\,x_0^\prime,c\,y_0^\prime\right)$ è una soluzione dell'equazione di partenza.
La nostra strategia sarà di trovare una soluzione particolare dell'equazione ridotta: $2x-31y=1$.
In generale si fa uso delle frazioni continue ma, nel nostro caso, è abbastanza evidente che $\left(16,1\right)$ è una soluzione. La soluzione generale è dunque
$\displaystyle \left\{\begin{array}{lC} x=16\cdot 39+31n=426+31n\\y=1\cdot 39+2n=39+2n \end{array}\right.$
Possiamo ottenerne una forma più comoda ponendo $n=k-19$
$\displaystyle \left\{\begin{array}{lC} x=35+31k\\y=1+2k \end{array}\right.$
Per ogni valore di $k$ c'è una soluzione ma non è detto che le componenti di questa soluzione siano il mcm e il MCD di una coppia di interi: dobbiamo trovare i valori di $k$ per cui ciò è vero.
Alcune considerazioni su mcm e MCD (tenete conto che per che fossero davvero rigorose bisognerebbe distinguere sempre il caso in cui $\text{MCD}\left(p,q\right)=1$, dato che $1$ non è primo: non c'ho palle...)
Primo, dati gli interi $p$ e $q$ sono unici $\text{MCD}\left(p,q\right)$ e $\text{mcm}\left(p,q\right)$. Infatti, se $P$ è l'insieme dei fattori primi di $p$ e $Q$ l'insieme dei fattori primi di $q$ allora $P\cap Q$ è l'insieme dei fattori primi di $\text{MCD}\left(p,q\right)$ e $P\cup Q$ è l'insieme dei fattori primi di $\text{mcm}\left(p,q\right)$. Unione e intersezione di due insiemi finiti sono definite univocamente.
Secondo, $\text{MCD}\left(p,q\right)$ e $\text{mcm}\left(p,q\right)$ non determinano univocamente una coppia $\left(p,q\right)$: per esempio, $\text{MCD}\left(10,105\right)=\text{MCD}\left(15,70\right)=5$ e $\text{mcm}\left(10,105\right)=\text{mcm}\left(15,70\right)=210$.
Usando il Principio di Inclusione-Esclusione, $P\cup Q=P+Q-P\cap Q$, otteniamo $x\,y=p\,q$. Questo significa che per ogni soluzione costituita di MCD e mcm è possibile che vi siano più coppie $\left(p,q\right)$.
Terzo, il MCD è sempre un divisore di mcm in quanto $P\cap Q$ è un sottoinsieme di $P\cup Q$.
Scriviamo dunque
$\displaystyle f\left(k\right)=\frac{35+31k}{1+2k}$
Quando $x=\text{MCD}\left(p,q\right)$ e $y=\text{mcm}\left(p,q\right)$, $f\left(k\right)$ è un intero, $n$. Abbiamo $f\left(0\right)=35$ e
$\displaystyle \lim_{k\to\infty}f\left(k\right)=\frac{31}2>15$
I valori possibili di $n$ sono dunque compresi tra $16$ e $35$: esplicitiamo l'equazione $f\left(k\right)=n$ rispetto a $k$
$\displaystyle k=\frac{35-n}{2n-31}$
e compiliamo la tabella
$\begin{array}{|c|c|c|}
\hline
n & \frac{35-n}{2n-31} & k \\
\hline
16 & \frac{19}{1} & 19 \\
\hline
17 & \frac{18}{3} & 6 \\
\hline
18 & \frac{17}{5} & \\
\hline
19 & \frac{16}{7} & \\
\hline
20 & \frac{15}{9} & \\
\hline
21 & \frac{14}{11} & \\
\hline
22 & \frac{13}{13} & 1 \\
\hline
& \vdots & \\
\hline
35 & \frac{0}{39} & 0 \\
\hline
\end{array}$
(ometto i numeri tra $22$ e $35$ perché danno una frazione minore di $1$)
Per $k = 0$ abbiamo $\left(x,y\right)=\left(35,1\right)$, $p\,q=5\cdot 7$ e le coppie $\left(1,35\right)$ e $\left(5,7\right)$.
Per $k=1$, abbiamo $\left(x,y\right) = \left(66,3\right)$, $p\,q=2\cdot 3^2\cdot 11$ e le coppie $\left(3,66\right)$ e $\left(6,33\right)$.
Per $k=6$, abbiamo $\left(x,y\right)=\left(221,13\right)$, $p\,q=13^2\cdot 17$ e la coppia $\left(13,221\right)$.
Infine, per $k=19$, abbiamo $\left(x,y\right)=\left(624,39\right)$, $p\,q=2^4\cdot 3^2\cdot 13^2$ e la coppia $\left(39,624\right)$.
Almeno spero
L'equazione $a\,x-b\,y=c$ ammette soluzioni intere se e solo $\text{MCD}\left(a,b\right)$ divide $c$. D'altra parte, nessuno scriverebbe mai l'equazione $15x-6y=9$: tutti la semplificherebbero immediatamente a $5x-2y=3$.
Consideriamo sunque solo equazioni per le quali $\text{MCD}\left(a,b\right)=1$, come del resto è nel nostro caso specifico.
Se l'equazione $a\,x-b\,y=c$ ammette soluzioni in $\mathbb{Z}^2$ allora ne ammette infinite. Se $\left(x_0,y_0\right)$ e $\left(x,y\right)$ sono due soluzioni della nostra equazione allora abbiamo che $a\,x_0-b\,y_0=a\,x-b\,y$: rimaneggiamo questa espressione per ottenere
$\displaystyle x-x_0=\frac{b\left(y-y_0\right)}a$
Dato che $x-x_0$ è un intero e che $a$ non divide $b$ allora $a$ deve dividere $\left(y-y_0\right)$. Con un ragionamento analogo troviamo che $b$ deve dividere $\left(x-x_0\right)$.
La soluzione generale della nostra equazione è quindi
$\displaystyle \left\{\begin{array}{lC} x=x_0+n\,b\\y=y_0+n\,a \end{array}\right.$
Alla nostra equazione corrisponde un'equazione "ridotta", $a\,x-b\,y=1$. Sia $\left(x_0^\prime,y_0^\prime\right)$ una soluzione particolare dell'equazione ridotta, ovvero
$\displaystyle a\,x_0^\prime-b\,y_0^\prime=1$
moltiplicando a destra e a sinistra per $c$, otteniamo
$\displaystyle a\,c\,x_0^\prime-b\,c\,y_0^\prime=a\,x_0-b\,y_0=c$
cioè, $\left(x_0,y_0\right)=\left(c\,x_0^\prime,c\,y_0^\prime\right)$ è una soluzione dell'equazione di partenza.
La nostra strategia sarà di trovare una soluzione particolare dell'equazione ridotta: $2x-31y=1$.
In generale si fa uso delle frazioni continue ma, nel nostro caso, è abbastanza evidente che $\left(16,1\right)$ è una soluzione. La soluzione generale è dunque
$\displaystyle \left\{\begin{array}{lC} x=16\cdot 39+31n=426+31n\\y=1\cdot 39+2n=39+2n \end{array}\right.$
Possiamo ottenerne una forma più comoda ponendo $n=k-19$
$\displaystyle \left\{\begin{array}{lC} x=35+31k\\y=1+2k \end{array}\right.$
Per ogni valore di $k$ c'è una soluzione ma non è detto che le componenti di questa soluzione siano il mcm e il MCD di una coppia di interi: dobbiamo trovare i valori di $k$ per cui ciò è vero.
Alcune considerazioni su mcm e MCD (tenete conto che per che fossero davvero rigorose bisognerebbe distinguere sempre il caso in cui $\text{MCD}\left(p,q\right)=1$, dato che $1$ non è primo: non c'ho palle...)
Primo, dati gli interi $p$ e $q$ sono unici $\text{MCD}\left(p,q\right)$ e $\text{mcm}\left(p,q\right)$. Infatti, se $P$ è l'insieme dei fattori primi di $p$ e $Q$ l'insieme dei fattori primi di $q$ allora $P\cap Q$ è l'insieme dei fattori primi di $\text{MCD}\left(p,q\right)$ e $P\cup Q$ è l'insieme dei fattori primi di $\text{mcm}\left(p,q\right)$. Unione e intersezione di due insiemi finiti sono definite univocamente.
Secondo, $\text{MCD}\left(p,q\right)$ e $\text{mcm}\left(p,q\right)$ non determinano univocamente una coppia $\left(p,q\right)$: per esempio, $\text{MCD}\left(10,105\right)=\text{MCD}\left(15,70\right)=5$ e $\text{mcm}\left(10,105\right)=\text{mcm}\left(15,70\right)=210$.
Usando il Principio di Inclusione-Esclusione, $P\cup Q=P+Q-P\cap Q$, otteniamo $x\,y=p\,q$. Questo significa che per ogni soluzione costituita di MCD e mcm è possibile che vi siano più coppie $\left(p,q\right)$.
Terzo, il MCD è sempre un divisore di mcm in quanto $P\cap Q$ è un sottoinsieme di $P\cup Q$.
Scriviamo dunque
$\displaystyle f\left(k\right)=\frac{35+31k}{1+2k}$
Quando $x=\text{MCD}\left(p,q\right)$ e $y=\text{mcm}\left(p,q\right)$, $f\left(k\right)$ è un intero, $n$. Abbiamo $f\left(0\right)=35$ e
$\displaystyle \lim_{k\to\infty}f\left(k\right)=\frac{31}2>15$
I valori possibili di $n$ sono dunque compresi tra $16$ e $35$: esplicitiamo l'equazione $f\left(k\right)=n$ rispetto a $k$
$\displaystyle k=\frac{35-n}{2n-31}$
e compiliamo la tabella
$\begin{array}{|c|c|c|}
\hline
n & \frac{35-n}{2n-31} & k \\
\hline
16 & \frac{19}{1} & 19 \\
\hline
17 & \frac{18}{3} & 6 \\
\hline
18 & \frac{17}{5} & \\
\hline
19 & \frac{16}{7} & \\
\hline
20 & \frac{15}{9} & \\
\hline
21 & \frac{14}{11} & \\
\hline
22 & \frac{13}{13} & 1 \\
\hline
& \vdots & \\
\hline
35 & \frac{0}{39} & 0 \\
\hline
\end{array}$
(ometto i numeri tra $22$ e $35$ perché danno una frazione minore di $1$)
Per $k = 0$ abbiamo $\left(x,y\right)=\left(35,1\right)$, $p\,q=5\cdot 7$ e le coppie $\left(1,35\right)$ e $\left(5,7\right)$.
Per $k=1$, abbiamo $\left(x,y\right) = \left(66,3\right)$, $p\,q=2\cdot 3^2\cdot 11$ e le coppie $\left(3,66\right)$ e $\left(6,33\right)$.
Per $k=6$, abbiamo $\left(x,y\right)=\left(221,13\right)$, $p\,q=13^2\cdot 17$ e la coppia $\left(13,221\right)$.
Infine, per $k=19$, abbiamo $\left(x,y\right)=\left(624,39\right)$, $p\,q=2^4\cdot 3^2\cdot 13^2$ e la coppia $\left(39,624\right)$.
Almeno spero
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Re: Una diofantea fra il mcm e il MCD.
Eccellente!
(Bruno)
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
Re: Una diofantea fra il mcm e il MCD.
Riporto il mio ragionamento, giusto perché lo avevo annotato.
L'equazione diofantea lineare 2·x - 31·y = 39 ha come soluzioni generali x = 31·t + 35 e y = 2·t + 1, velocemente ottenute osservando che y dev'essere dispari e ponendo quindi y = 2·t + 1, con t intero scelto a piacere.
Ora, dobbiamo considerare che 31·t + 35 e 2·t + 1 (t ≥ 0) siano, rispettivamente, il minimo comune multiplo e il massimo comune divisore dei due numeri cercati a, b.
Per una nota proprietà, (31·t + 35)·(2·t + 1) = a·b e questo significa che (31·t + 35)/(2·t + 1) dev'essere intero, pertanto dev'essere intero anche il rapporto (19 - t)/(2·t + 1) = (31·t + 35)/(2·t + 1) - 16, ciò che avviene quando t = 0, 1, 6, 19.
Da questi valori abbiamo facilmente, volendo a < b:
x = 35 = 5·7, y = 1 → (a, b): (1, 35), (5, 7);
x = 66 = 3·22 = 6·11, y = 3 → (a, b): (3, 66), (6, 33);
x = 221 = 13·17, y = 13 → (a, b): (13, 221);
x = 624 = 39·16, y = 39 → (a, b): (39, 624).
Il massimo comune divisore (y) e il minimo comune multiplo (x), dunque, costituiscono una coppia risolvente il problema, ma nel primo e nel secondo caso abbiamo due coppie ulteriori.
Buon anno a tutti
L'equazione diofantea lineare 2·x - 31·y = 39 ha come soluzioni generali x = 31·t + 35 e y = 2·t + 1, velocemente ottenute osservando che y dev'essere dispari e ponendo quindi y = 2·t + 1, con t intero scelto a piacere.
Ora, dobbiamo considerare che 31·t + 35 e 2·t + 1 (t ≥ 0) siano, rispettivamente, il minimo comune multiplo e il massimo comune divisore dei due numeri cercati a, b.
Per una nota proprietà, (31·t + 35)·(2·t + 1) = a·b e questo significa che (31·t + 35)/(2·t + 1) dev'essere intero, pertanto dev'essere intero anche il rapporto (19 - t)/(2·t + 1) = (31·t + 35)/(2·t + 1) - 16, ciò che avviene quando t = 0, 1, 6, 19.
Da questi valori abbiamo facilmente, volendo a < b:
x = 35 = 5·7, y = 1 → (a, b): (1, 35), (5, 7);
x = 66 = 3·22 = 6·11, y = 3 → (a, b): (3, 66), (6, 33);
x = 221 = 13·17, y = 13 → (a, b): (13, 221);
x = 624 = 39·16, y = 39 → (a, b): (39, 624).
Il massimo comune divisore (y) e il minimo comune multiplo (x), dunque, costituiscono una coppia risolvente il problema, ma nel primo e nel secondo caso abbiamo due coppie ulteriori.
Buon anno a tutti
(Bruno)
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
Re: Una diofantea fra il mcm e il MCD.
Solo dopo aver risolto il quesito con un procedimento analogo a quelli riportati, mi sono accorto che la diofantea lineare può essere tranquillamente aggirata.
Se $ 2x-31y=39$ dove $ x $ ed $y $ sono, rispettivamente, il mcm ed il MCD dei numeri cercati, deve essere $ x=ry $; sostituendo si ottiene $ 2ry-31y=y(2r-31)=39 $. I due fattori devono essere divisori di $39$: quindi $ 2r-31 | 39 $ con quattro possibilità:
$ 2r-31=1 $, da cui $ r=16, y=39/1=39$;
$ 2r-31=3 $, da cui $ r=17, y=39/3=13$;
$ 2r-31=13 $, da cui $ r=22, y=39/13=3$;
$ 2r-31=39 $, da cui $ r=35, y=39/39=1 $.
Per ogni coppia di valori $ r,y $ il numero di soluzioni $ a, b $ è uguale a $ 1 $ se $ r=1$, altrimenti a $ 2^(n-1) $ con $ n $ uguale al numero di divisori primi distinti di $ r $.
Nel caso generale, con equazione $ ex-fy=g $ è raro che tutti i divisori di $ g $ siano accettabili: deve infatti essere $ r=(d_i+f)/e $, dove $d_i$ è un divisore di $g$, e questo si verifica solo per quei divori congruenti a $-f $ modulo $ e $.
L'unica utilità dell'equazione diofantea lineare credo consista nel riconoscere immediatamente l'assenza di soluzioni, quando $ e $ ed $ f $ abbiano un fattore comune che non divide $ g $.
Ciao
Se $ 2x-31y=39$ dove $ x $ ed $y $ sono, rispettivamente, il mcm ed il MCD dei numeri cercati, deve essere $ x=ry $; sostituendo si ottiene $ 2ry-31y=y(2r-31)=39 $. I due fattori devono essere divisori di $39$: quindi $ 2r-31 | 39 $ con quattro possibilità:
$ 2r-31=1 $, da cui $ r=16, y=39/1=39$;
$ 2r-31=3 $, da cui $ r=17, y=39/3=13$;
$ 2r-31=13 $, da cui $ r=22, y=39/13=3$;
$ 2r-31=39 $, da cui $ r=35, y=39/39=1 $.
Per ogni coppia di valori $ r,y $ il numero di soluzioni $ a, b $ è uguale a $ 1 $ se $ r=1$, altrimenti a $ 2^(n-1) $ con $ n $ uguale al numero di divisori primi distinti di $ r $.
Nel caso generale, con equazione $ ex-fy=g $ è raro che tutti i divisori di $ g $ siano accettabili: deve infatti essere $ r=(d_i+f)/e $, dove $d_i$ è un divisore di $g$, e questo si verifica solo per quei divori congruenti a $-f $ modulo $ e $.
L'unica utilità dell'equazione diofantea lineare credo consista nel riconoscere immediatamente l'assenza di soluzioni, quando $ e $ ed $ f $ abbiano un fattore comune che non divide $ g $.
Ciao
Re: Una diofantea fra il mcm e il MCD.
Ottimo, Gnugnu
La 'diofantea', in realtà, nella mia risoluzione l'ho appena sfiorata, quasi un tocco di piuma
La 'diofantea', in realtà, nella mia risoluzione l'ho appena sfiorata, quasi un tocco di piuma
(Bruno)
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}
...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}