Moduli di base

[Ayra]

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

[Drago96]

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

[Ayra]

Argh, bella gaffe xD
In ogni caso, giusto un chiarimento: per "combinare i risultati" cosa intendi esattamente? asd

[Alepedra96]

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

[Drago96]

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

[simone256]

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 )
Grazie in anticipo

[Ayra]

Perfetto, ora tutto chiaro, grazie mille

[LeZ]

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 )
Grazie in anticipo

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

[Ayra]

mmm...quindi perchè un numero nella forma ak+b sia un quadrato perfetto è necessario che b sia residuo quadratico modulo k, giusto?

[Drago96]

Esatto
Attenzione che è necessario, ma non sufficiente...