Il resto

Ieri avevo postato la seguente domanda:

Qual'è il resto della seguente divisione intera?

2¹⁰⁰¹ mod 31

(dove l'operazione mod indica appunto il resto della divisione fra i due numeri interi. Ad esempio, 16 mod 7 = 2).

La risposta corretta è 2. Siete stati bravissimi naturalmente, e velocissimi! La mia domanda sul tempo di risposta aveva un fondamento "scientifico": stiamo preparando il test di ammissione a questo corso. Il test consisterà di una serie di domande a risposta multipla. Una sezione è dedicata a quiz di questo tipo, e vorrei capire quanto ci metterebbe in media uno con una laurea triennale in informatica a rispondere a questo quesito. Naturalmente i 10 lettori del mio blog non sono un campione significativo, lo so, era giusto per gigioneggiare. Tipicamente, prevediamo 2 minuti a risposta, per 60 domande mettiamo un limite di 2 ore circa (e senza PC con python a disposizione, non so se mi spiego ... :) ). Metteremo un test di esempio sul sito, magari poi ve lo passo e potrete divertirvi a sapere se sareste ammessi al nostro corso!

Tornando al problema, si tratta un tipico calcolo di aritmetica modulare, una branca molto bella della matematica. Nell'informatica si usa per tante cose, principalmente in crittografia. Di sotto elaboro un minimo le soluzioni di Zar e Riccardo.

Nell'aritmetica modulare, due numeri interi p e r si dicono congruenti modulo q, e si scrive

p = r (mod q)

se esiste un intero k tale che

q = k p + r.

L'aritmetica modulare ha delle proprietà simili a quelle dell'aritmetica normale. Qui ci interessano le seguenti:

per qualunque intero c, se p = r (mod q) allora c p = c r (mod q) (1)

per qualunque intero k, se p = r (mod q) allora p^k = r^k (mod q) (2)

Sono entrambe banalmente dimostrabili e ve ne potete convincere con qualche piccola prova.
Nel nostro caso specifico, è ovvio che

2⁵ = 1 (mod 31)

Usando la relazione (2), possiamo scrivere

2¹⁰⁰⁰ = (2⁵)²⁰⁰ = 1 (mod 31)

A questo punto, sfruttando (1), si conclude

2¹⁰⁰¹ = 2 (mod 31)

Va beh, scusate, l'ho fatta lunghissima, ci ho messo quasi 1220 mod 11 minuti a scrivere 'sto post!