Uso dell'aritmetica modulare

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Uso dell'aritmetica modulare

Messaggio da Willy67 » 05 dic 2009, 21:42

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
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 » 06 dic 2009, 12:37

perchè nessuno risponde? :?

Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto » 06 dic 2009, 14:06

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?
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 06 dic 2009, 14:53

impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 » 06 dic 2009, 16:47

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ì

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 06 dic 2009, 17:29

e' che molti strumenti si basano sull'aritmetica modulare come
http://it.wikipedia.org/wiki/Piccolo_teorema_di_Fermat
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 » 09 dic 2009, 15:44

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

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 09 dic 2009, 15:56

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)
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 » 09 dic 2009, 16:04

hai ragione sai

Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 » 09 dic 2009, 16:09

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?

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 09 dic 2009, 16:31

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

qualche lettura interessante
viewtopic.php?t=3489
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Claudio.
Messaggi: 697
Iscritto il: 29 nov 2009, 21:34

Messaggio da Claudio. » 09 dic 2009, 21:47

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
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 09 dic 2009, 22:11

$ 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.
Messaggi: 697
Iscritto il: 29 nov 2009, 21:34

Messaggio da Claudio. » 09 dic 2009, 22:16

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
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 09 dic 2009, 22:31

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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Rispondi