stavo cercando una spiegazione al teorema del resto cinese,ho cercato nel glossario,ma mi linkava una pagina che poi risultava inesistente...
grazie in anticipo
teorema del resto cinese
per "spiegazione" intendi come si usa, cosa vuol dire moralmente, o una dimostrazione?
l'unica cosa che mi piace dire adesso è la risposta alla seconda domanda (le altre sono più noiosette): moralmente il teorema cinese ti dice che le classi di resto modulo m ed n (interi primi tra loro) sono "indipendenti modulo mn", nel senso che se tu scegli una classe di resto modulo m ed una modulo n ne trovi una unica modulo mn che discende a queste due classi.
detto in parole "più povere" (ovvero nascondendo per un attimo le classi di resto), dati due interi a,b esistono infiniti interi c tali che c dia lo stesso resto di a nella divisione per m e lo stesso resto di b nella divisione per n, e tutti questi interi differiscono per multipli di mn.
era quello che volevi sentirti dire? spero di essere stato vagamente chiaro...
l'unica cosa che mi piace dire adesso è la risposta alla seconda domanda (le altre sono più noiosette): moralmente il teorema cinese ti dice che le classi di resto modulo m ed n (interi primi tra loro) sono "indipendenti modulo mn", nel senso che se tu scegli una classe di resto modulo m ed una modulo n ne trovi una unica modulo mn che discende a queste due classi.
detto in parole "più povere" (ovvero nascondendo per un attimo le classi di resto), dati due interi a,b esistono infiniti interi c tali che c dia lo stesso resto di a nella divisione per m e lo stesso resto di b nella divisione per n, e tutti questi interi differiscono per multipli di mn.
era quello che volevi sentirti dire? spero di essere stato vagamente chiaro...
Re: teorema del resto cinese
Basta sostituire "dm.unibo" a "dm.unipi" o "ing.unipi".Noemi91x ha scritto: mi linkava una pagina che poi risultava inesistente...
Anyway:
viewtopic.php?t=3355&highlight=teorema+cinese+resto
viewtopic.php?t=9586&highlight=teorema+cinese+resto
Ciao!
Sapere aude!
ti ringrazio...non so se posso postare qui questo esercizio o sarebbe meglio in tdn..comunque..intanto lo scrivo qui.
Determinare quale resto si ottiene dividendo 2006^2006 per 90.
Non saprei in realtà come procedere,cioè una volta che noto che:
2006^2006=0 mod 2
2006^2006=1 mod 5
2006^2006=1 mod 9
come proseguo?scusate la domanda banale
Determinare quale resto si ottiene dividendo 2006^2006 per 90.
Non saprei in realtà come procedere,cioè una volta che noto che:
2006^2006=0 mod 2
2006^2006=1 mod 5
2006^2006=1 mod 9
come proseguo?scusate la domanda banale
-
GioacchinoA
- Messaggi: 137
- Iscritto il: 13 feb 2009, 15:44
- Località: Bari
Allora cerco di scriverti come farei io.
Chiamo per semplicità $ 2006^{2006}=x $
So che
$ x \equiv 0 \pmod{2} $
$ x \equiv 1 \pmod{5} $
$ x \equiv 1 \pmod{9} $
Risolvo prima il sistema costituito dalla prima congruenza e la seconda.
$ x \equiv 0 \pmod{2} $
$ x \equiv 1 \pmod{5} $
Sappiamo che per il TCR c'è una sola soluzione definita modulo 10. Dobbiamo trovarla.
Dalla prima congruenza si ricava $ x=2k $ e dalla seconda si ricava $ x-5h=1 $ per $ k,h \in \mathbb{Z} $.
Quindi $ 2k = 5h+1 \Rightarrow 2k-5h=1 $. Una soluzione è $ k=3,h=1 $.
Sostituendo dunque si trova $ x \equiv 6 \pmod{10} $
Il primo sistema è equivalente al sistema costituito da quest'ultima congruenza e dall'ultima. Quindi ora bisogna risolvere
$ x \equiv 6 \pmod{10} $
$ x \equiv 1 \pmod{9} $
Sappiamo che per il TCR c'è una sola soluzione definita modulo 90. Dobbiamo trovarla.
Dalla prima congruenza si ricava $ x = 10a+6 $ e dalla seconda si ricava $ x = 9b+1 $ per $ a,b \in \mathbb{Z} $. Per confronto(come abbiamo fatto prima) ottengo $ 10a+6 = 9b+1 \Rightarrow 9b-10a = 5 $. Una soluzione è $ b=5,a=4 $
Sostituendo, dunque, si trova $ x \equiv 46 \pmod{90} $ che è la soluzione del sistema e quindi il resto di $ x=2006^{2006} $ quando viene diviso per 90.
Chiamo per semplicità $ 2006^{2006}=x $
So che
$ x \equiv 0 \pmod{2} $
$ x \equiv 1 \pmod{5} $
$ x \equiv 1 \pmod{9} $
Risolvo prima il sistema costituito dalla prima congruenza e la seconda.
$ x \equiv 0 \pmod{2} $
$ x \equiv 1 \pmod{5} $
Sappiamo che per il TCR c'è una sola soluzione definita modulo 10. Dobbiamo trovarla.
Dalla prima congruenza si ricava $ x=2k $ e dalla seconda si ricava $ x-5h=1 $ per $ k,h \in \mathbb{Z} $.
Quindi $ 2k = 5h+1 \Rightarrow 2k-5h=1 $. Una soluzione è $ k=3,h=1 $.
Sostituendo dunque si trova $ x \equiv 6 \pmod{10} $
Il primo sistema è equivalente al sistema costituito da quest'ultima congruenza e dall'ultima. Quindi ora bisogna risolvere
$ x \equiv 6 \pmod{10} $
$ x \equiv 1 \pmod{9} $
Sappiamo che per il TCR c'è una sola soluzione definita modulo 90. Dobbiamo trovarla.
Dalla prima congruenza si ricava $ x = 10a+6 $ e dalla seconda si ricava $ x = 9b+1 $ per $ a,b \in \mathbb{Z} $. Per confronto(come abbiamo fatto prima) ottengo $ 10a+6 = 9b+1 \Rightarrow 9b-10a = 5 $. Una soluzione è $ b=5,a=4 $
Sostituendo, dunque, si trova $ x \equiv 46 \pmod{90} $ che è la soluzione del sistema e quindi il resto di $ x=2006^{2006} $ quando viene diviso per 90.