Una diofantea fra il mcm e il MCD.

[Bruno]

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.

[panurgo]

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

[Bruno]

Eccellente!

[Bruno]

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

[gnugnu]

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

[Bruno]

Ottimo, Gnugnu

La 'diofantea', in realtà, nella mia risoluzione l'ho appena sfiorata, quasi un tocco di piuma