se io ho una congruenza $ \displaystyle a\equiv b(modc) $, come posso "manipolare" il modulo? Ad esempio, a quanto è congruo $ $a $ modulo $ $c^n $?
magari è una domanda stupida, ma non ho trovato niente al riguardo...
ancora congruenze?!?!?
-
HarryPotter
- Moderatore
- Messaggi: 354
- Iscritto il: 01 gen 1970, 01:00
- Località: Pavia
Qua si guadagna informazione spudoratamente
Dire che un numero $ a $ è conguro a $ b $ modulo $ c $, significa dire che esiste un numero intero $ k $ tale che $ a= kc + b $.
Di conseguenza non posso dire esattamente quale sia il resto di $ a $ diviso $ c^n $, perché potrebbe essere uguale a $ a=k_0c^n + b $ oppure $ a=k_1c^n + (c + b) $ fino a $ a=k_{c^n-c}c^n + (c^n-c +b) $. Tutte quante queste espressioni mi rispettano la congruenza iniziale $ a\equiv b\pmodc $. Per fare un esempio: 2, 7, 12, 17, 22 sono tutti congrui a 2 modulo 5, ma hanno diversa congruenza modulo 25.
Viceversa se so che $ a\equiv b\pmod{c^n} $ posso dire che $ a\equiv b\pmod{c} $. Infatti dall'espressione $ a= kc^n + b $, ricavo $ a= (kc^{n-1})c + b $.
Più in generale se ho $ a\equiv b\pmod{pq} $ con $ p $ e $ q $ primi tra loro, per il teorema cinese del resto questa congruenza è equivalente al sistema di congruenze formato da $ a\equiv b\pmod{p} $ e $ a\equiv b\pmod{q} $. Esempio: dire che un numero è congruo a 4 modulo 15 è equivalente a dire che un numero è congruo a 4 (cioè 1) modulo 3 e che è congruo a 4 (cioé -1) modulo 5.
Se vogliamo astrarre un principio generale, diciamo che un modulo grande e con tanti divisori (tipo 64, 120) mi dà più informazioni, cioé mi fissa meglio il numero di un modulo piccolo (tipo 2 o 3).
Prova a farti qualche esempio e vedrai che tutto ti sarà chiaro. Sulle schede olimpiche di Gobbino è tutto spiegato per bene.
Ciao ciao
Di conseguenza non posso dire esattamente quale sia il resto di $ a $ diviso $ c^n $, perché potrebbe essere uguale a $ a=k_0c^n + b $ oppure $ a=k_1c^n + (c + b) $ fino a $ a=k_{c^n-c}c^n + (c^n-c +b) $. Tutte quante queste espressioni mi rispettano la congruenza iniziale $ a\equiv b\pmodc $. Per fare un esempio: 2, 7, 12, 17, 22 sono tutti congrui a 2 modulo 5, ma hanno diversa congruenza modulo 25.
Viceversa se so che $ a\equiv b\pmod{c^n} $ posso dire che $ a\equiv b\pmod{c} $. Infatti dall'espressione $ a= kc^n + b $, ricavo $ a= (kc^{n-1})c + b $.
Più in generale se ho $ a\equiv b\pmod{pq} $ con $ p $ e $ q $ primi tra loro, per il teorema cinese del resto questa congruenza è equivalente al sistema di congruenze formato da $ a\equiv b\pmod{p} $ e $ a\equiv b\pmod{q} $. Esempio: dire che un numero è congruo a 4 modulo 15 è equivalente a dire che un numero è congruo a 4 (cioè 1) modulo 3 e che è congruo a 4 (cioé -1) modulo 5.
Se vogliamo astrarre un principio generale, diciamo che un modulo grande e con tanti divisori (tipo 64, 120) mi dà più informazioni, cioé mi fissa meglio il numero di un modulo piccolo (tipo 2 o 3).
Prova a farti qualche esempio e vedrai che tutto ti sarà chiaro. Sulle schede olimpiche di Gobbino è tutto spiegato per bene.
Ciao ciao