In Sat, 28 Nov 2020 23:44:34 +0100, El Filibustero
Post by El FilibusteroPost by DanoPost by El FilibusteroQual 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