OliForum Matematico

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

perchè nessuno risponde?

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?

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

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ì

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

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??

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)

hai ragione sai

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?

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

qualche lettura interessante
viewtopic.php?t=3489

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?

$ 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.

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 ^^

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.