Allenamenti di matematica:Teoria dei numeri e algebra modulare

Soluzioni esercizi29 novembre 2013

1. Canguro salterino. Un canguro salterino si trova ai piedi di una scala infinita che intende salire nel seguentemodo:

• Salta avanti di 3 gradini e in seguito indietreggia di 1 gradino

• Salta avanti di 5 gradini e in seguito indietreggia di 3 gradini

• Salta avanti di 7 gradini e in seguito indietreggia di 5 gradini

• ...

Quali gradini compresi tra il 2000-esimo e il 2017-esimo (estremi inclusi) non visitera il canguro? In generale suquali gradini non mettera mai piede?

Dimostrazione. Il canguro avanza secondo la sequenza 3 − 1 + 5 − 3 + 7 − 5 + .... Se raggruppiamo i terminidue a due otteniamo (3 − 1) + (5 − 3) + (7 − 5) + ... = 2 + 2 + 2 + ... da cui appare chiaro che tutti i gradinipari vengono visitati. Similmente se raggruppiamo i termini due a due escludendo il primo otteniamo 3 + (−1 +5) + (−3 + 7) + (−5 + 9) + ... = 3 + 4 + 4 + 4 + ... da cui si vede che anche i gradini nella forma 4k + 3 vengonovisitati. Gli unici esclusi sono tutti e soli quelli della forma 4k + 1, pertanto il canguro non visita il 2001-esimo,il 2005-esimo, il 2009-esimo, il 2013-esimo e il 2017-esimo gradino.

2. Settantasettesette. Un numero e composto da 77 cifre decimali tutte uguali a 7. Qual e il resto della suadivisione per 101?

Dimostrazione. Sia N il numero composto da 77 cifre 7. Sfruttando la base decimale otteniamo N =∑76

i=0 7 ·10i.Ora notiamo che

10 ≡ 10 (mod 101) 102 ≡ −1 (mod 101) 103 ≡ 10 ·102 ≡ −10 (mod 101) 104 ≡ 102 ·102 ≡ 1 (mod 101)

Pertanto

N =

18∑i=0

7(104i + 104i+1 + 104i+2 + 104i+3) + 7 · 1076 ≡18∑i=0

7(+1 + 10− 1− 10) + 7 · 1 ≡ 7 (mod 101)

quindi resto della divisione di N per 101 e 7.

3. Quadrati nascosti (1). Siano a, b interi positivi. Se 132ab e 63ab2 sono entrambe quadrati perfetti, qual e ilminimo valore di a + b?

Dimostrazione. Se 63ab2 e un quadrato allora anche 63a deve esserlo; poiche 63 = 32 · 7 il minimo valore di ache rende 63a un quadrato e a = 7.Passando al secondo numero e sostituendo troviamo 132ab = 132 · 7 · b.Poiche 132 = 22 ·3·11 il minimo valore di b che rende 132ab = 22 ·3·7·11·b un quadrato perfetto e b = 3·7·11 = 231.Quindi a + b = 238 (effettivamente 63ab2 = 48512 e 132ab = 4622).

4. Quadrati nascosti (2). Trovare l’unico primo p per cui 11p + 1 e un quadrato perfetto.

Dimostrazione. 11p + 1 e un quadrato perfetto se esiste un n intero tale che n2 = 11p + 1. Questa stessaespressione si puo scrivere nella forma

11p = n2 − 1 = (n− 1)(n + 1).

Poiche pero p e primo, la sua fattorizzazione contiene solo 2 elementi; ci sono due possibilita: la prima e

{n− 1, n + 1} = {1, n2 − 1},

il che implica n = 0 o n = 2, nessuna delle quali e ammessa poiche 11 | (n2 − 1) e quindi (n2 − 1) > 11.Consideriamo allora la seconda possibile fattorizzazione, per cui

{n− 1, n + 1} = {11, p};

si puo avere n + 1 = 11 e quindi n − 1 = 9, che pero non e primo e quindi non va bene; oppure si puo averen− 1 = 11 e quindi n + 1 = 13, che e primo. La soluzione e quindi p = 13.

1

5. Potenze impressionanti (1). Determinare la cifra delle unita di 2137763.

Dimostrazione. E sufficiente scrivere l’espansione in base 10 di 2137 ed elevarla ad una potenza qualsiasi perverificare che la cifra delle unita del risultato dipende solo dalla cifra delle unita della base (7 nel nostro caso).Ora cerchiamo la periodicita della cifra delle unita delle potenze di 7: 71 = 7, 72 = 49, 73 = 343, 74 = 2401 e,siccome abbiamo ottenuto 1, da qui in avanti si ripetera la sequenza 7, 9, 3, 1.Pertanto il periodo con cui si ripetono e 4, poiche 763 ≡ 3 (4) la cifra delle unita cercata e 3.

6. Potenze impressionanti (2). Determinare la cifra delle unita di 33...3

dove compaiono esattamente cento 3.

Dimostrazione. Analogamente a prima studiamo il periodo delle potenze di 3: 31 = 3, 32 = 9, 33 = 27, 34 = 81,quindi il periodo e 4. Pertanto siamo interessati a determinare la congruenza modulo 4 dell’esponente di 3,

ovvero E = 33...3

dove compaiono 99 numeri 3.Osserviamo che

E = 33...3

≡ (−1)3...3

≡ −1 ≡ 3 (mod 4)

dove la penultima congruenza segue dal fatto che l’esponente di −1 e sicuramente dispari. Abbiamo quindiottenuto che i novantanove 3 all’esponente del numero fornito nel problema sono congrui a 3 modulo 4, ne segueche la cifra richiesta dal problema e la terza nel periodo delle potenze di 3, ovvero 7.

7. Primi nascosti (1). Per quali valori interi di n il numero n2 − 14n + 24 e primo?

Dimostrazione. E sufficiente fattorizzare N = n2− 14n+ 24 = (n− 2)(n− 12) e notare che tale numero e primose e solo se uno dei suoi due fattori e 1 o −1 e l’altro e un primo (con segno adeguato). Basta analizzare i quattrocasi:

• n− 2 = 1 =⇒ n = 3 =⇒ 3− 12 = −9 =⇒ N = −9 non accettabile

• n− 2 = −1 =⇒ n = 1 =⇒ 1− 12 = −11 =⇒ N = 11 accettabile

• n− 12 = 1 =⇒ n = 13 =⇒ 13− 2 = 11 =⇒ N = 11 accettabile

• n− 12 = −1 =⇒ n = 11 =⇒ 11− 2 = 9 =⇒ N = −9 non accettabile

Quindi gli unici valori di n per cui N e primo sono n = 1, 13.

8. Primi nascosti (2). Trovare il piu grande intero n tale che tutti i numeri n + 1, n + 3, n + 7, n + 9, n + 13 en + 15 siano primi.

Dimostrazione. L’intero cercato e n = 4. Infatti, per n = 1 il numero n+3 = 4 non e primo, per n = 2 il numeron + 7 = 9 non e primo, per n = 3 il numero n + 3 = 4 non e primo. Per n > 4 tutti i numeri sono maggiori di 5e almeno uno e divisibile per 5. Infatti, i numeri 1, 3, 7, 9, 13, 15, se divisi per 5, danno come resti della divisione1, 3, 2, 4, 3, 0, ovvero tutti i possibili resti. Pertanto i numeri n + 1, n + 3, n + 7, n + 9, n + 13, n + 15 danno tuttii possibili resti di una divisione per 5 e almeno uno di questi e divisibile per 5 e quindi non e primo. Per n = 4,invece, otteniamo i numeri primi 5, 7, 11, 13, 17, 19.

9. Soluzioni intere. Quali numeri interi n risolvono l’equazione (n2 − n− 1)(n+2) = 1?

Dimostrazione. Se a, b sono numeri interi (anche negativi) l’equazione della forma ab = 1 ha soluzioni se e solose a = 1, a = −1 e b e pari oppure b = 0 e a 6= 0. Consideriamo i vari casi:

• (n2 − n− 1) = 1 =⇒ n = −1, 2 entrambe accettabili

• (n2 − n − 1) = −1 =⇒ n = 0, 1. Se n = 0 l’esponente e pari e la soluzione e accettabile, mentre se n = 1l’esponente e dispari e la soluzione non e accettabile

• n + 2 = 0 =⇒ n = −2 =⇒ 22 + 2− 1 = 5 6= 0 e accettabile

I valori di n cercati sono n = −2,−1, 0, 2.

10. Iperbole. Quali coppie di numeri naturali (a, b) appartengono al grafico dell’iperbole a2 − 4b2 = 45 ?

Dimostrazione. Scomponendo otteniamo (a + 2b)(a− 2b) = 45 = 32 · 5. Ricordando che a, b sono naturali segueche a + 2b deve essere maggiore di a− 2b, pertanto i casi da considerare sono:

• a + 2b = 45, a− 2b = 1 =⇒ (a, b) = (23, 11)

• a + 2b = 15, a− 2b = 3 =⇒ (a, b) = (9, 3)

• a + 2b = 9, a− 2b = 5 =⇒ (a, b) = (7, 1)

2

11. Terne occulte. Determinare tutte le terne di numeri naturali (p, n,m) con p primo tali che pn + 144 = m2.

Dimostrazione. Si ottiene facilmente che pn = (m + 12)(m − 12). Sicuramente non puo essere m + 12 = 1,altrimenti m− 12 < 0, mentre se m− 12 = 1 si ottiene la soluzione (5, 2, 13).Altrimenti, poiche p e un primo, i due fattori a destra devono essere potenze (in generale distinte) del primo p.Siano ph = m + 12 e pk = m − 12, allora ph − pk = 24 =⇒ pk(ph−k − 1) = 24, quindi le uniche possibilita perpk sono pk = 2, 3, 4, 8. Dal caso pk = 3 si ottiene la soluzione (3, 4, 15), mentre dal caso pk = 8 si ottiene lasoluzione (2, 8, 20); gli altri casi non portano a soluzioni accettabili.

12. Divisibilita (1). Sia n un intero dispari. Mostrare che 8 divide n2 − 1.

Dimostrazione. Poiche n e dispari, si puo scrivere nella forma n = 2k + 1 per un certo intero k. Quindi avremon2 − 1 = (2k + 1)2 − 1 = 4k2 + 4k = 4k(k + 1). Dato che k e k + 1 sono due interi consecutivi, uno dei due sarapari e quindi anche il loro prodotto lo sara. Dunque 2 divide k(k + 1), da cui 8 divide 4k(k + 1).

13. Divisibilita (2). Provare che 36n − 26n e divisibile per 35 per qualsiasi intero n.

Dimostrazione. Sia N = 36n − 26n; sappiamo che 35 = mcm(5, 7), quindi per dimostrare che 35 | N bastadimostrare che 5 | N e 7 | N . Innazitutto si ha

N = 36n − 26n = 93n − 43n

≡ 43n − 43n (mod 5)

≡ 0 (mod 5)

e quindi 5 | N . Allo stesso modo

N = 36n − 26n = 272n − 82n

≡ (−1)2n − 12n (mod 7)

≡ 1n − 1n (mod 7)

≡ 0 (mod 7)

e quindi 7 | N .

14. Combinazioni vincenti. Mischiare le cifre {1, 2, 3, 4, 5, 6, 7, 8} per creare un numero divisibile per 11.

Dimostrazione. Il trucco e creare una sequenza di numeri che, sottratti a coppie, diano una serie di +1 e −1 chealla fine si annullino a vicenda. E facile trovare 1− 2 + 4− 3 + 5− 6 + 8− 7 = −1 + 1− 1 + 1 = 0. Quindi unasoluzione e 12435687.

15. Il numero magico. Se cambi la mia ultima cifra con un 9 e la mia prima cifra con un 5 troverai il quadrato diun terzo della mia nona parte. Un ultimo indizio: sono un numero di 3 cifre. Chi sono?

Dimostrazione. Sia n il numero che stiamo cercando e sia y la sua seconda cifra. Allora

(1

3· 1

9n)2 = 509 + 10y.

Nel membro di destra deve esserci il quadrato di un numero intero e quindi troviamo 529, da cui y = 2. Dunque127n = 23, ovvero n = 621.

16. Diofanto. L’infanzia di Diofanto occupo un sesto della sua vita, la giovinezza un dodicesimo ed egli fu celibeper un settimo della sua vita. Ebbe un figlio cinque anni dopo essersi sposato, il quale visse la meta degli annidel padre e Diofanto stesso morı 4 anni dopo di lui. A che eta morı Diofanto?

Dimostrazione. Sia x l’eta di Diofanto. Allora

x− 4− ((1

6+

1

12+

1

7)x + 5) =

1

2x,

da cui

(1

2− (

1

6+

1

12+

1

7))x = 9,

ovvero 328x = 9 e x = 84.

3

17. Questioni di differenze. Dati a, b, c, d interi mostrare che 12|(a− b)(a− c)(a− d)(b− c)(b− d)(c− d).

Dimostrazione. Mostrare la divisibilita per 12 equivale a mostrare separatamente che N = (a − b)(a − c)(a −d)(b − c)(b − d)(c − d) e multiplo di 3 e di 4 (osserviamo che nella scrittura di N compaiono tutte le possibilidifferenze tra a, b, c, d a meno dell’ordine).

• Divisibilita per 3. Le classi di congruenza modulo 3 sono 0, 1, 2, siccome ognuno tra a, b, c, d apparterraad esattamente una di esse avremo almeno due numeri nella stessa classe di equivalenza. Pertanto la lorodifferenza e un multiplo di 3 e anche N sara un multiplo di 3.

• Divisibilita per 4. Le classi di equivalenza modulo 4 sono 0, 1, 2, 3. Se almeno due tra a, b, c, d appartengonoalla stessa classe di equivalenza allora N e multiplo di 4, altrimenti a, b, c, d devono stare necessariamentein classi di equivalenza diverse. A meno dell’ordine delle differenze otteniamo N ≡ (3− 2)(3− 1)(3− 0)(2−1)(2− 0)(1− 0) ≡ 12 ≡ 0 (mod 4). Quindi in tutti i casi N e divisibile per 4.

Pertanto N e divisibile per 12.

18. Estremamente quadrato. Mostrare che se 2 + 2√

28n2 + 1 e un intero, allora e un quadrato perfetto.

Dimostrazione. Se 2 + 2√

28n2 + 1 e intero, allora 28n2 + 1 deve essere il quadrato perfetto di un numero dispari28n2 + 1 = (2m + 1)2.

28n2 + 1 = 4m2 + 4m + 1

7n2 = m(m + 1)

Poiche al primo membro compare il prodotto tra un primo e un quadrato perfetto sia hanno due possibilita:

• m = a2 e m + 1 = 7b2: questo e impossibile poiche dovrebbe essere 7b2 − a2 = 1 ma tramite i residuiquadratici modulo 4 risulta impossibile.

• m = 7c2 e m + 1 = d2: segue

2 + 2√

28n2 + 1 = 2 + 2(2m + 1) = 4m + 4 = 4(m + 1) = 4d2 = (2d)2

19. IMO 1974/3. Provare che∑n

k=0

(2n+12k+1

)23k non e divisibile per 5 per nessun n ≥ 0.

Dimostrazione. Sia a =√

8 allora

(1 + a)2n+1 =

2n+1∑i=0

(2n + 1

i

)12n+1−iai = 1 +

2n+1∑i=1

(2n + 1

i

)ai

effettuando la sostituzione i = 2k + 1 sull’indice della sommatoria otteniamo:

1 +

2n+1∑i=1

(2n + 1

i

)ai = 1 +

n∑k=0

(2n + 1

2k + 1

)a2k+1 = 1 + a

n∑k=0

(2n + 1

2k + 1

)a2k

Chiamiamo ora s = 1 e t =∑n

k=0

(2n+12k+1

)a2k (osserviamo che t e proprio l’espressione a cui siamo interessati).

La relazione precedente diviene (1+a)2n+1 = s+at e con passaggi analoghi si ottiene anche (1−a)2n+1 = s−at.Moltiplicando membro a membro le due relazioni trovate si ottiene (ricordando a =

√8): 72n+1 = s2 − 8t2. Se

per assurdo fosse t ≡ 0 (mod 5) allora 72n+1 ≡ s2 (mod 5), tuttavia cio e impossibile perche 72k+1 ≡ 2, 3 (mod 5)mentre i residui quadratici modulo 5 sono 0, 1,−1. Pertanto t =

∑nk=0

(2n+12k+1

)a2k non e mai divisibile per 5.

20. Congruenze a tappeto. Determinare per quanti interi n ≥ 2 la congruenza x25 ≡ x (modn) e vera per ognix.

Dimostrazione. Per il Teorema Cinese del Resto si ha:

(m,n) = 1 x25 ≡ x (modmn) ⇐⇒ x25 ≡ x (modm) x25 ≡ x (modn)

Quindi possiamo limitarci a cercare i primi p tali che x25 ≡ x (mod pr) con r ≥ 1.Se fosse r > 1 allora 0 ≡ (pr−1)25 ≡ pr−1 (mod pr) ma cio e impossibile perche pr−1 6≡ 0 (mod pr). Quindir = 1 e possiamo semplificare la relazione nel seguente modo x24 ≡ 1 (mod p). Per il Piccolo Teorema di Fermat(p − 1)|24 e questo porta a p = 2, 3, 5, 7, 13. Tutti i numeri n cercati sono quindi il prodotto di uno o piu deiprimi trovati, ovvero

(51

)+(52

)+(53

)+(54

)+(55

)= 25 − 1 = 31.

4

21. IMO 1988/6. Siano a, b interi positivi tali che ab+1 divide a2 + b2, mostrare che a2+b2

ab+1 e un quadrato perfetto.

Dimostrazione. Per assurdo supponiamo esista k = a2+b2

ab+1 che non sia un quadrato perfetto. Tra tutte le possibilisoluzioni consideriamo la soluzione (A,B) tale che A+B sia il minimo possibile e senza perdita di generalita siaA ≥ B. Sostituiamo A con x nella relazione iniziale ed otteniamo un’equzione di secondo grado x2 − (kB)x +(B2 − k) = 0 avente una radice uguale ad A. L’altra radice e ottenibile tramite le formule di Viete (o relazioni

radici-coefficienti) x2 = kB − A = B2−kA . Dalla prima equazione si vede che x2 e intero e dalla seconda che e

non nullo, se lo fosse si avrebbe k = B2 ma noi abbiamo supposto che k non sia un quadrato perfetto. Inoltrex2 non puo essere negativo perche altrimenti si avrebbe

−kBx2 > k

x22 − kBx2 + (B2 − k) > x2

2 + k + B2 − k > x22 + B2 > 0

che e una contraddizione. Infine, ricordando A ≥ B abbiamo:

x22 =

B2 − k

A< A

x22 + B < A + B

che contraddice la minimalita della coppia (A,B). Tale assurdo e derivato dal fatto di aver supposto inizialmente

l’esistenza di un k non quadrato perfetto tale che k = a2+b2

ab+1 .

5