Moduli di base

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Ayra
Messaggi: 9
Iscritto il: 25 giu 2012, 15:19

Moduli di base

Messaggio da Ayra » 25 giu 2012, 15:38

Salve, scusate se la domanda è stupida, ma ho iniziato da poco con l'aritmetica modulatoria e ho qualche dubbio.
Lavorando su questa dispensa http://www.dmi.units.it/divulgazione/ma ... oniche.pdf, ho trovato un esercizio in cui mi si chiede di calcolare 2618259 mod n per n=5,15,21 e altri numeri facilmente scomponibili sfruttando i risultati di un esercizio precedente in cui avevo già calcolato per n=2,3,4,5 e altri numeri i cui criteri di congruenza sono noti. La domanda è: che relazione lega le due cose? Se per esempio devo fare 2618259 mod 15, in che modo mi aiuta sapere 2618259 mod 3 e 2618259 mod 5?
Grazie in anticipo e scusate il disturbo :wink:
"Esiste, indipendentemente dalla mente umana, una realtà matematica pura e immutabile." A. Connes

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Moduli di base

Messaggio da Drago96 » 25 giu 2012, 16:03

Perchè poi ti basta combinare i risultati per far venire la congruenza modulo il numero composto.
Per esempio, $2618259\equiv 0\pmod3$ e $2618259\equiv 4\pmod5$ e vedi facilmente che $2618259\equiv 9\pmod{15}$

P.S: si dice aritmetica modulare ;)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
Ayra
Messaggi: 9
Iscritto il: 25 giu 2012, 15:19

Re: Moduli di base

Messaggio da Ayra » 25 giu 2012, 16:15

Argh, bella gaffe xD
In ogni caso, giusto un chiarimento: per "combinare i risultati" cosa intendi esattamente? asd
"Esiste, indipendentemente dalla mente umana, una realtà matematica pura e immutabile." A. Connes

Avatar utente
Alepedra96
Messaggi: 46
Iscritto il: 04 giu 2012, 17:36
Località: Vercelli

Re: Moduli di base

Messaggio da Alepedra96 » 25 giu 2012, 17:54

Ti aiuta perchè ti fa capire che il risultato è multiplo di 3 ma è anche multiplo di 5 aumentato di 4, è il più piccolo numero con questa caratteristica è 9 :D
Ci sono tre tipi di persone nel mondo: quelle che sanno contare e quelle che non sanno contare.

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Moduli di base

Messaggio da Drago96 » 25 giu 2012, 17:55

Nel senso: vedi cosa è quella roba modulo 3 e modulo 5; po ti scrivi tutti i numeri congrui a 0 modulo 3 da 0 a 14 (in questo caso) e fai la stessa cosa per il modulo 5.
Avrai due "liste": 0,3,6,9,12 e 4,9,14; ora ti basta trovare l'elemento comune, in questo caso 9, che è proprio il risultato che stavamo cercando ;)

Posso fare queste cose perchè il Teorema Cinese dice che in un sistema di congruenze, con i moduli a due a due coprimi (nel nostro caso 3 e 5), esiste un'unica soluzione modulo il prodotto dei moduli (nel nostro caso 15=3*5)

Per trovarla puoi usare questo metodo, oppure quest'altro, che però è meno immediato e più complicato:
Testo nascosto:
Dato il sistema (con $(m_i,m_j)=1$ )
$\displaystyle\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\ \vdots \\ x\equiv a_n\pmod{m_n}\end{cases}$
per $i\in\{1,\dots,n\}$ prendi $\displaystyle b_i=\prod_{j\neq i}m_j$ e $c_i=b_i^{-1}\pmod{m_i}$.
Allora $\displaystyle x\equiv\sum_{i=1}^n a_i\cdot b_i\cdot c_i\pmod{m_1\cdot m_2\cdots m_n}$
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Moduli di base

Messaggio da simone256 » 25 giu 2012, 23:01

Scusa Drago ma non ho capito l'ultimo metodo che hai scritto! Che cosa significa la notazione "i diverso da j" sotto la produttoria? Ha un nome questo metodo che me lo cerco? :-)
Chiedo una cosa che ho già postato senza successo riguardante la teoria dei numeri...
Per quali n...
28k^3 + 24k^2 + 3k - 1
...è un quadrato perfetto?
è della stessa dispensa di Ayra (non per nulla consigliata sempre da Drago :mrgreen: )
Grazie in anticipo :D
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

Avatar utente
Ayra
Messaggi: 9
Iscritto il: 25 giu 2012, 15:19

Re: Moduli di base

Messaggio da Ayra » 25 giu 2012, 23:33

Perfetto, ora tutto chiaro, grazie mille :D
"Esiste, indipendentemente dalla mente umana, una realtà matematica pura e immutabile." A. Connes

LeZ
Messaggi: 284
Iscritto il: 08 mag 2011, 21:28

Re: Moduli di base

Messaggio da LeZ » 28 giu 2012, 14:20

simone256 ha scritto:Scusa Drago ma non ho capito l'ultimo metodo che hai scritto! Che cosa significa la notazione "i diverso da j" sotto la produttoria? Ha un nome questo metodo che me lo cerco? :-)
Chiedo una cosa che ho già postato senza successo riguardante la teoria dei numeri...
Per quali n...
28k^3 + 24k^2 + 3k - 1
...è un quadrato perfetto?
è della stessa dispensa di Ayra (non per nulla consigliata sempre da Drago :mrgreen: )
Grazie in anticipo :D
$ 28k^3+24k^2+3k-1 = (2k+1)^2\cdot{(7k-1)}=l^2 $
Il primo fattore è sempre un quadrato perfetto, mentre $ 7k-1 $ non è mai un quadrato perfetto in quanto $ -1 $ non è un residuo quadratico modulo $ 7 $.

Avatar utente
Ayra
Messaggi: 9
Iscritto il: 25 giu 2012, 15:19

Re: Moduli di base

Messaggio da Ayra » 03 lug 2012, 14:47

mmm...quindi perchè un numero nella forma ak+b sia un quadrato perfetto è necessario che b sia residuo quadratico modulo k, giusto?
"Esiste, indipendentemente dalla mente umana, una realtà matematica pura e immutabile." A. Connes

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Moduli di base

Messaggio da Drago96 » 03 lug 2012, 15:29

Esatto ;)
Attenzione che è necessario, ma non sufficiente...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Rispondi