venerdì 9 aprile 2010

Il resto

Ieri avevo postato la seguente domanda:

Qual'è il resto della seguente divisione intera?

21001 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 pk = rk (mod q) (2)
Sono entrambe banalmente dimostrabili e ve ne potete convincere con qualche piccola prova.
Nel nostro caso specifico, è ovvio che
25 = 1 (mod 31)
Usando la relazione (2), possiamo scrivere
21000 = (25)200 = 1 (mod 31)
A questo punto, sfruttando (1), si conclude
21001 = 2 (mod 31)
Va beh, scusate, l'ho fatta lunghissima, ci ho messo quasi 1220 mod 11 minuti a scrivere 'sto post!

1 commento:

  1. Se Python non vale allora calc:

    $ calc
    C-style arbitrary precision calculator (version 2.12.3.3)
    Calc is open software. For license details type: help copyright
    [Type "exit" to exit, or "help" for help.]

    ; 2^1001%31
    2
    ; quit

    Ma ho dovuto installarlo e non c'era in Sys V, allora bc:

    $ bc
    bc 1.06.94
    Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
    This is free software with ABSOLUTELY NO WARRANTY.
    For details type `warranty'.
    2^1001%31
    2
    quit

    Non vale nemmeno bc? Qui vi volevo, se fossero tutti come voi Galileo...
    Adesso chiamo Cota e gli dico di dirlo alla Gelmini.
    E potrei sempre coinvolgere Gabriella Carlucci.

    RispondiElimina

I commenti vengono gestiti tramite Disqus. Siete pregati di autentificarvi prima di commentare.