Congruenze
Trovare la cifra dell’unità dei seguenti numeri 20132013 [3]
20142014 [6]
20152015 [5]
(basta fare una congruenza modulo 10)
Trovare la cifra dell’unità e la cifra delle decine dei seguenti numeri 19511951 [51]
20072007 [43]
(basta fare una congruenza modulo 100)
SISTEMI DI Congruenze - problema 1
Alberto, Beppe e Carlo vogliono trovarsi dopo il capodanno una sera per rievocare i bei vecchi tempi.
Alberto ha una serata libera ogni 6 giorni a partire dal 2 di Gennaio, Beppe ha invece una sola serata libera ogni 15 giorni a partire dall’11 e Carlo ne ha una libera ogni 8 giorni a partire dal 5.
Quando riusciranno a incontrarsi tutti e tre?
E se invece Alberto e Beppe vogliono incontrarsi da soli?
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31
[x è congruo a 2 mod 6, x è congruo a 11 mod 15, x è congruo a 5 mod 8. Il sistema formato dalle precedenti congruenze è impossibile (x deve essere pari per la prima condizione e dispari per la terza). Mettiamo a sistema solo le prime due e procediamo per tentativi, elencando le soluzioni della seconda (che sono di meno, avendo un modulo più grande). La soluzione è, pertanto, x congruo a 26 mod 30, dove 30 = mcm(6,15).]
Per approfondire la teoria, si può fare riferimento al Teorema cinese del resto.
SISTEMI DI Congruenze - problema 2
Dato un certo numero di cose, si sa che:
- dividendolo per 3 dà come resto 2, - dividendolo per 5 dà come resto 3, - dividendolo per 7 dà come resto 2.
Qual è il numero?
[x è congruo a 2 mod 3, x è congruo a 3 mod 5, x è congruo a 2 mod 7. La soluzione è 23 + 105k]
SISTEMI DI Congruenze - problema 3
Una contadina porta delle uova al mercato.
Sa che contandole a 2 a 2 ne avanzava 1, contandole a 3 a 3 ne avanzava 1,
a 4 a 4 ne avanzava 1, a 5 a 5 ne avanzava 1, a 6 a 6 ne avanzava 1 e
contandole a 7 a 7 aveva un numero esatto.
Quante sono le uova?
[301]
Le nove Muse, portando ognuna lo stesso numero di corone, incontrano le tre Grazie e distribuiscono a loro delle corone, così tutte ne hanno lo stesso numero. Quante sono le corone (scegli il numero minimo possibile)?
[è un multiplo di 9 e di 12, il minimo possibile è 36]
ALGORITMO di euclide
Calcolare il M.C.D. tra due numeri naturali a e b : a = 1705 b = 625
1705 : 625 = 2 resto di 455 625 : 455 = 1 resto di 170 455 : 170 = 2 resto di 115 170 : 115 = 1 resto di 55
115 : 55 = 2 resto di 5 l’ultimo resto non nullo è il M.C.D. di a e b 55 : 5 = 11 resto di 0
Allora si può scrivere 5 = 115 + (-2) 55
= 115 + (-2) (170 + (-1) 115) = 115 + (-2) 170 + (2) 115 = (3) 115 + (-2) 170
= (3) [455 + (-2) 170] + (-2) 170 = (3) 455 + (-6) 170 + (-2) 170 = (3) 455 + (-8) 170 = (3) 455 + (-8) [625 + (-1) 455] = (3) 455 + (-8) 625 + (8) 455 = (11) 455 + (-8) 625
= (11) [1705 + (-2) 625] + (-8) 625 = (11) 1705 + (-22) 625 + (-8) 625 = (11) 1705 + (-30) 625 5 = (11) 1705 + (-30) 625
Identità di bézout
Se a e b sono interi (non entrambi nulli) e il loro massimo comune divisore è d, allora esistono due interi x e y tali che
a x + b y = d
Equazione diofantea
è un’equazione in una o più incognite a coefficienti interi di cui si ricercano le soluzioni intere.
• lineari (di primo grado) : identità di Bézout
• quadratiche : ne è un esempio l’equazione di Pell x2 - a y2 = 1
• xn + yn = zn ha infinite soluzione per n = 2 (terne pitagoriche), mentre non ne ha alcuna per n > 2 (ultimo teorema di Fermat dimostrato da Wiles nel 1994)
Trovare le soluzioni intere per l’equazione:
86x + 25y = 1
[si applica l’algoritmo di Euclide e si ottiene x = − 9 + 25k e y = 31 − 86k, dove k è un qualsiasi intero]
problema
Cinque uomini fanno naufragio su un’isola; non c’è nulla da mangiare tranne noci di cocco. Essi vanno a dormire ripromettendosi di dividersele la mattina seguente.
Nel mezzo della notte, uno dei naufraghi sente improvvisamente fame e decide di prendersi subito la sua parte di noci di cocco. Nel farlo, scopre che se ne toglie una sono esattamente divisibili per cinque. Decide pertanto di dare una noce di cocco ad una scimmia che si trova nei paraggi e di prendersi la sua parte. Durante la notte, ognuno degli altri marinai fa la stessa cosa all’insaputa dell’altro, e ognuno trova un numero di noci di cocco che diventa divisibile per cinque una volta donata una noce di cocco alla scimmia. Al mattino, decidono come d’accordo di dividere il mucchio delle noci in parti uguali, e ne trovano ancora una di resto da lasciare alla scimmia. Quante erano all’inizio, come minimo, le noci di cocco?
x = numero iniziale di noci di cocco
dopo il primo marinaio ne restano 4/5 (x - 1) che è un numero intero
dopo il secondo marinaio ne restano 4/5 [4/5 (x - 1) - 1] = 16/25 x - 36/25 dopo il terzo ne restano 4/5 (16/25x - 36/25 - 1) = 64/125 x - 244/125
dopo il quarto ne restano 4/5 (64/125x - 244/125 - 1) = 256/625 x - 1476/625
dopo il quinto ne restano 4/5 (256/625x - 1476/625 - 1) = 1024/3125 x - 8404/3125 1024/3125 x - 8404/3125 - 1 = 5 y
[15621]
Un esercizio
Trovare le soluzioni intere positive dell’equazione:
xy + x = 2007y + 2
Svolgimento:
• non è possibile scomporre questo polinomio
• portiamo tutto al primo membro e proviamo a togliere 2005 a entrambi i membri otteniamo xy + x − 2007y − 2005 − 2 = − 2005 ⇔ (x − 2007)·(y + 1) = −2005
• il fattore negativo deve essere (x − 2007)
• 2005 = 1 · 5 · 401
PROBLEMI PROPOSTI
Sia x la somma degli interi dispari da 1 a 2k + 1. Quali di questi valori non può assumere x?
(A) 625 (B) 1225 (C) 2025 (D) 3025 (E) 4525
[la somma dei primi n numeri dispari è n2, perciò dobbiamo cercare un valore che non sia un quadrato perfetto (E)]
La cifra delle unità del numero 2137753 è:
(A)1 (B)3 (C)5 (D)7 (E)9
[basta fare la congruenza modulo 10 e si ottiene D]
Quanto vale la somma delle cifre di (999.999.999.999.995)2 ?
[facendo la congruenza modulo 9 e si ottiene 25, però così perdiamo le informazioni sui 9;
per tentativi 952 = 9025, 9952 = 990025, 99952 = 99900025, ... , il nostro numero avrà 9 ripetuto 14 volte e finisce per 25;
oppure (1015 - 5)2 = 1030 - 1016 + 25]
Fonti:
http://www.dmi.units.it/divulgazione/matCultSoc/olimpia10/gomut/dispense_olimpioniche.pdf http://www.science.unitn.it/~tasso/applicazioni-euclide.pdf
https://it.wikipedia.org/wiki/Identit%C3%A0_di_B%C3%A9zout http://utenti.quipo.it/base5/index.htm
Antonella Guerrieri, Stefania Lippiello, Liceo G.B. Brocchi, Bassano del Grappa, a.s. 2015/16