Uso dell'aritmetica modulare

[Willy67]

Ciao a tutti, siccome mi sono iscritto a questo forum con il principale scopo di imparare, e ho visto usare molto spesso l'aritmetica modulare, vorrei cercare di comprendere il suo uso in problemi del tipo:"Determina le ultime due cifre di $ 8^{254} + 5^{254} $" Oppure il famoso problema olimpico di Archimede di quest'anno "$ \frac {66^{66}}{2} $ " in cui bisognava trovare la cifra delle unità. Spero mi possiate aiutare visto che mi pare di capire sia una cosa molto importante nei problemi olimpici e nella matematica in generale. Grazie mille a tutti

[Willy67]

perchè nessuno risponde?

[Nonno Bassotto]

Ciao, e benvenuto sul forum. Innanzitutto sposto la tua domanda nel glossario, visto che si tratta di un chiarimento e non di un problema.

Per rispondere alla tua domanda prima vorrei capire se ti è chiaro come funziona l'aritmetica modulare. Cioè, sai lavorare con le congruenze ma non sai risolvere questi problemi oppure desideri imparare da zero cosa sono le congruenze?

[SkZ]

http://it.wikipedia.org/wiki/Aritmetica_modulare
un po' di teoria non guasta

[Willy67]

Diciamo che so cos'è una congruenza e un po' di sue proprietà viste su wikipedia ( simmetrica, transitiva ecc.. ). Per il resto ne so veramente poco, ma ho visto che la utlizzate spesso qui nel forum per risolvere problemi così

[SkZ]

e' che molti strumenti si basano sull'aritmetica modulare come
http://it.wikipedia.org/wiki/Piccolo_teorema_di_Fermat

[Willy67]

beh che molti streumenti si basino sull'uso dell'aritmetica modulare lo posso capire, ma voi, che si suppone siate ragazzi del triennio come me... come fate a risolvere ad esempio il problema $ 66^66 $ - -> trovare la cifra delle unità, con le congruenze??

[SkZ]

ne' Nonno Bassotto, ne' io siamo piu' liceali

cmq basta le proprieta' in wiki per farlo.
2 cose:
$ $66^{66} $ termina per 6 (qualunque potenza di un numero che termina per 6 termina per 6)
$ $\frac{66^{66}}{2} $ e' pari
ergo $ $\frac{66^{66}}{2} $ termina per 8 (deve terminare per 3 o 8, ma essendo pari non puo' terminare per 3)

[Willy67]

hai ragione sai

[Willy67]

skz ma secondo te quali sono i requisiti di conoscenza per svolgere almeno la prima prova di Archimede con il massimo?
Perchè io quest'anno l'ho fatta la prima volta... e devo dire che ho fatto un punteggio pessimo infatti ho perso molto tempo nei primi esercizi ( soprattutto quello dei paggi) e non ho nemmeno avuto il tempo di leggerli tutti. Ora: credo che il mio problema sia stato dovuto alla mancanza di familiarità con i problemi... ma magari conoscendo qualche nozione teorica in più sarei stato più avvantaggiato. Ad esempio per il problema combinatorio bisognava riconoscere che le combinazioni delle 5 vocali ripetendole in 4 spazi sono 5^4.. ecc.
Il mio obbiettivo è il prossimo anno di prendere 125 su 125: cosa posso fare per prepararmi al meglio?

[SkZ]

lavorare, lavorare, lavorare
hai 14 Giochi di Archimede da farti, buon lavoro

qualche lettura interessante
viewtopic.php?t=3489

[Claudio.]

Io avrei lo stesso dubbio, poichè mi sono accostato alle congruenze solo da qualche giorno...
Prendiamo in considerazione proprio il quesito di cui parlava lui:
Quanto vale l'ultima cifra di
$ \frac{66^{66}}{2} $

Può essere risolto in questo modo:
$ \frac{66^{66}}{2}=2^{65}\cdot 3^{66}\cdot 11^{66} \equiv 2\cdot 9 \cdot 1=8 \pmod {10} $
Capisco benissimo il metodo, solo che non so come si faccia a capire quanto valga per esempio $ 2^{65} \pmod{10} $
senza calcolare la potenza. Ci si arriva per logica o c'è un metodo per risalire a quanto è congruo in un certo modulo?

[EvaristeG]

$ 2^0\equiv 1 $
$ 2^1\equiv 2 $
$ 2^2\equiv 4 $
$ 2^3\equiv 8\equiv -2\equiv-2^1 $
quindi
$ 2^4=2\cdot2^3\equiv -2^2=-4 $
$ 2^5=2^2\cdot2^3\equiv-2^3=-8\equiv2 $
e quindi vedi bene che ora le cose si ripetono: se
$ 2^5\equiv 2^1 $ allora
$ 2^{4+a}\equiv2^{a} $ (se a>0).
dunque ti basta considerare il resto dell'esponente quando è diviso per 4:
se il resto è 0 (ma l'esponente NON è 0) 2^a è 6 modulo 10
se il resto è 1, 2^a è 2 modulo 10
se il resto è 2, 2^a è 4 modulo 10
se il resto è 3, 2^a è 8 modulo 10.
Se l'esponente è proprio 0, il resto ovviamente è 1.
65=64+1=4(16)+1
quindi il resto è 2.

[Claudio.]

Ma questo vale solo per il 2....quindi devo dedurre che non esiste un metodo preciso...Grazie per la velocità con cui hai risposto comunque ^^

[Tibor Gallai]

48 è pari, perché è il doppio di 24.
Ma questo vale solo per il 48, quindi devo dedurre che non esiste un metodo preciso per stabilire se un numero è pari.