Discussione:
Giochino 61: le monete
(troppo vecchio per rispondere)
El Filibustero
2020-11-27 08:44:20 UTC
Permalink
Qual e' la massima somma (intera) che NON puo' essere pagata mediante
monete di valore (intero) x e y, con x e y coprimi? Ciao
Dano
2020-11-28 22:30:29 UTC
Permalink
In Fri, 27 Nov 2020 09:44:20 +0100, El Filibustero
Post by El Filibustero
Qual e' la massima somma (intera) che NON puo' essere pagata mediante
monete di valore (intero) x e y, con x e y coprimi? Ciao
xy-x-y
--
Dano
El Filibustero
2020-11-28 22:44:34 UTC
Permalink
Post by Dano
Post by El Filibustero
Qual e' la massima somma (intera) che NON puo' essere pagata mediante
monete di valore (intero) x e y, con x e y coprimi? Ciao
xy-x-y
Esatto. Perche'? Ciao
Dano
2020-11-29 13:36:47 UTC
Permalink
In Sat, 28 Nov 2020 23:44:34 +0100, El Filibustero
Post by El Filibustero
Post by Dano
Post by El Filibustero
Qual e' la massima somma (intera) che NON puo' essere pagata mediante
monete di valore (intero) x e y, con x e y coprimi? Ciao
xy-x-y
Esatto. Perche'? Ciao
Dal libro Aritmetica Superiore di Harold Davenport

Dati a e b naturali e primi fra loro, il piu' grande intero positivo n
che non sia esprimibile come ax+by, con x e y interi e maggiori di 1,
e' n=ab-a-b

Dimostrazione:
Intanto, se n = ab-a-b, allora n+a = b(a+1) e' divisibile per b.
Sia n = ax + by con x, y >= 0.
Allora n+a = a(x+1)+by, e pertanto a(x+1) e' multiplo di b,
e anche x+1 deve esserlo, in quanto h = MCD(a,b) = 1.
Siccome x non e' negativo, avremo allora x+1 >= b,
da cui n = ax+by >= a(b-1) = ab-b, un assurdo.
Inversamente, supponiamo n >= ab-a-b+1, e sia x il minimo numero
naturale per cui n-ax e' divisibile per b. Siccome h=1, un tale x
esistera' e sara' tale che 0 <= x <= b-1.
Avremo n = ax+by, e il problema e' dimostrare che y >= 0.
Se cosi' non fosse, avremmo y <= -1, e dunque n <= ax-b <= a(b-1)-b =
ab-a-b, in contraddizione con l'ipotesi iniziale.
--
Dano
Elio Fabri
2020-12-01 20:18:41 UTC
Permalink
Post by Dano
Dal libro Aritmetica Superiore di Harold Davenport
Dati a e b naturali e primi fra loro, il piu' grande intero positivo n
che non sia esprimibile come ax+by, con x e y interi e maggiori di 1,
e' n=ab-a-b
Intanto, se n = ab-a-b, allora n+a = b(a+1) e' divisibile per b.
...
Nella dim. che citi c'è un banale errore di segno: sarà
n+a = b(a-1).
Non ho controllato se questo sia o no influente nel seguito, perché
ero interessato a un altro aspetto: come arrivare al risultato.

E' una tradizione universale della matematica di spendere molte
più energie di docenti e discenti nel presentare e imparare
dimostrazioni che nel capire come si scoprono i risultati che *poi* si
dimostrano rigorosamente.
A mia conoscenza il solo che si sia occupato diffusamente di questo
aspetto fu George Polya: scrisse diversi libri sul tema (io ne ho
qualcuno).

Nella fattispecie, ho lavorato sulla cosa. Quello che ho trovato non è
molto, ma non può essere riassunto qui. Lo presento in

http://www.sagredo.eu/temp/numeri.pdf
--
Elio Fabri
Continua a leggere su narkive:
Loading...