Sistema congruenze e equazioni lineari congruenti

[matax]

Salve ho un problema su questo sistema di congruenze

x ≡ −44 (mod 48)
x ≡ 72 (mod 28)

l'unico passaggio che ho fatto è portarlo nella forma

x ≡ 4(mod 48)
x ≡ 16 (mod 28)

poi ho pensato di applicare il teorema cinese del resto, ma MCD(48,28) = 4, quindi non sono coprimi e non posso applicare il teorema e non so come andare avanti.

Altra cosa mi sono imbattuto in questa equazione lineare modulo n
x^11 ≡ 25 (mod 62)

Io ho sempre visto equazioni del tipo
ax ≡ b (mod n)
in cui basta calcolare l'inverso di a e poi trovare le soluzioni.

Grazie in anticipo

[hamming_burst]

Ciao, visto che sto preparando un esame che tratta anche questi argomenti, mi faccio un po' di esercizio e ti dò na mano.

${(x -= −44 mod 48),(x -= 72 mod 28) :}$ è un sistema di congruenze, come giustamente hai detto il sistema:

${(x -= 4 mod 48),(x -= 16 mod 28) :}$ è equivalente, io userò quest'ultimo e la chiamerò Sol.

Te hai fatto un minestrone con un altro tipo di esercizio, cioè con le equazioni lineari mod n o con crittografia RSA.)

Ti dico i passaggi fondamentali poi fai te.

Allora prima si calcola il MCD:

$ 28 = 7 * 2^2 $
$ 48 = 3 * 2^4$
quindi risulta che $(28,48) = 2^2 = 4$ Controllo la compatibilità del sistema:
$(28,48)$|$16-4$
$4$|$12$ OK Quindi per il teorema cinese del resto $ Sol != 0$ Inoltre $16-4=12=3*(28,48)=3*4$

Calcolo la soluzione particolare con Euclide:

$48=1*28+20$ | $20 = (1)48 + (-1)28$
$28=1*20+8$ | $8=(1)28 + (-1)20$
$20=2*8+4$ | $4 = (1)20 + (-2)8$
$8=2*4+0$

$4=(1)20 + (-2)8= (1)20 + (-1)((1)28 + (-1)20) = (-2)28 + (3)20 = (-2)28 + (3)((1)48 + (-1)28) = (3)48 + (-5)28$
Quindi:

$16-4 = 12 = 3*((3)48 + (-5)28) = (9)48 + (-15)28$
$16 - 4 = (9)48 + (-15)28$
$16 - (9)48 = 4 + (-15)28$
$-416=-416$

Ne segue che c=-416 è una soluzione particolare.
Calcolo m.c.m:

$[28,48] = (28*48)/((28,48)) = 336$

$Sol = {-416 + k[28,48]\ |\ kinZZ} = [-416]_336 = [256]_336$

Spero sia chiaro, questi sono i più facili da calcolare, per l'altra equazione te la scriverò dopo, è un po' lungo usare MathLB. Se hai dubbi basta scrivere. Ciao

PS: ti conviene andarti a presentare, che se no i moderatori ti linciano.

EDIT:
aggiornate le formule

[matax]

ok oggi ci sono stato su tutto il giorno e ne ho fatti alcuni guardando degli esercizi risolti dal mio docente e penso di aver capito.
in questo esercizio sono arrivato fino
16 - 4 = 12 = 3 * 4 = 3 [3(48)-5(28)] = 9 * 48 - 15 * 28
come te ma poi ho fatto
16 + 15*28 = 4 + 9*48 = 436
da cui
x ≡ 436 (mod 336) ===> x ≡ 100 (mod 336)

ho sbagliato?

ps mi vado subito a presentare e ti ringrazio per l'aiuto appena hai tempo mi spighi quella con esponente?

[hamming_burst]

Allora rispondo alla tua prima domanda sul primo sistema.
Te la divisione euclidea la hai risolta, ma hai fatto uno sbaglio nello scambio nella combinazione lineare, i segni non li devi cambiare. Ti faccio un esempio: $ a - b = (+h)x + (-k)y $ dove $a mod x $ e $b mod y$ diventa $ a - (+h)x = b + (-k)y $ informalmente: te scambi solo le "lettere", gli operatori (i meno e i più centrali) non gli tocchi $a$ va con $x$ e $b$ va con $y$. Poi deve diventare un'uguaglianza $-416 = -416$ se guardi i miei calcoli capisci perchè.

Per l'altro esercizio, allora:

Questo è la base della crittografia RSA (bellissimi sti esercizi se fatti con la teoria).

$ x^11 -= 25 mod 62 $

Primo passo, controllare che 25 e 62 siano coprimi, cioè che non abbiano moltiplicatori comuni o che l'unico moltiplicatore è 1 (sono numeri primi)

$ 25 = 5^2$
$62 = 31*2$
Quindi, l'unico moltiplicatore comune è 1. (25,62) = 1.
Perciò 25 è invertibile mod 62. Se esiste soluzione x, allora x deve essere invertivile mod 62.

Trovo $\Phi(62) = \Phi(31*2) = \Phi(31) * \Phi(2) = (31-1)*(2-1) = 30$
Controllo che $(11,30) = 1$ sono coprimi, quindi 11 è invertibile mod 30

Adesso applichi il Teorema di Fermat-Eulero, se $d in [11]_30^-1$ cioè $d $è invetibile di $11 mod 30$ allora $[25^d]_62$ è l'inversa della soluzione e $d >- 0$

Trovo $ d$ con l'algoritmo di Euclide:

$ 30 = 2*11+8 $ | $ 8 = (1)30 + (-1)11$
$11 = 1*8+3$ | $ 3 = (1)11 + (-1)8 $
$8=2*3+2$ | $2 = (1)8 + (-2)3 $
$3=1*2+1$ | $1 = (1)3 + (-1)2$
$2=2*1+0$

$1 = (1)3 + (-1)2 = (1)3 + (-1)((1)8 + (-2)3) = (-1)8 + (3)3 = (-1)8 + (3)((1)11 + (-1)8) = (3)11 + (-4)8 = (3)11 + (-4)((1)30 + (-1)11) = (-4)30 + (11)11$

Quindi l'inverso di $11 mod 30$ è: $[11]_30^-1 = [11]_30$
Perciò $d=11$ e l'inversa della soluzione è:

$ [25^11]_62 = 25^11 = (5^3)^7 * 5 -= [125=2*62+1]_62^7 * [5]_62 = [1^7]_62 * [5]_62 = [5]_62 $

Quindi la soluzione dell'equazione è: $[25^11]_62 = [5]_62 $

Forse questo è un po' più complesso da comprendere, ma se studi la teoria, sti quattro passaggi sono facili e sempre tutti uguali. L'ultima parte quella della scomposizione utilizzo i teoremi e le definizioni delle classi di equivalenza. Penso sia tutto giusto, lo ho fatto in poco tempo, comunque i passaggi sono quelli.
Se hai domande basta farle. Ciao

[mistake89]

scusate se mi intrometto... ma la formulazione del Teorema cinese del resto afferma che gli interi siano a due a due coprimi.
in questo caso non è così e non capisco cosa è stato applicato...

(magari con algebra 1 solamente non sono in grado di comprenderlo!)

[matax]

la riscrivo meglio perchè a me viene ancora così anche seguendo il tuo secondo ragionamento
16 - 4 = 12 = 3 * 4 = 3 [(3)48+(-5)*28] = (9) * 48 + (-15) * 28
come te ma poi ho fatto
16 - (-15)*28 = 4 + (9)*48 = 436
da cui
x ≡ 436 (mod 336) ===> x ≡ 100 (mod 336).

per quella con l'esponente ti ringrazio ho capito come si fanno e mi risultano uguali

[hamming_burst]

@matax: Hai ragione te, ho erroneamente scambiato i valori, leggendo 28 per un 48 sorry. Il risultato è una classe 100 mod 336. Come ti sembrano, non sono difficili vero?

@mistake89: Hai ragione, il teorema dice proprio questo. Ma se viene interpretato per un sistema di congruenze generale e applicando un altra parte del teorema cinese del resto, cioè quello che dice, "Tutte le soluzione del sistema sono la classe della soluzione mod il minimo comune multiplo delle relazioni di equivalenza delle congruenze". Se non sei convinto vedila così, per risolvere tali sistemi la condizione neccessaria e sufficiente è che: se $ { (x -= a mod n) , (x-=b mod m):} $deve essere che$ (n,m) $divide$ a-b$. n e m devono avere un moltiplicatore comune o equivalentemente che lo abbiano uguale a $+-1$ (coprimi, vedi la definizione completa). Se non è chiaro basta chiedere.

[NightKnight1]

${ (x -= 4 (mod 48) ),(x -= 16 (mod 28)) :}$.
Osservo che $28=4 \times 7$ e che $48=16 \times 3$. E che 4 e 7 sono coprimi e che 16 e 3 sono coprimi. Allora per il teorema cinese del resto:
$x -= 4 (mod 48)$ è equivalente a $x -= 4 (mod 16) \ , \ x -= 4 (mod 3)$
$x -= 16 (mod 28)$ è equivalente a $x -= 16 (mod 4) \ , \ x -= 16 (mod 7)$.
Allora il sistema è equivalente a :
${ (x -= 4 (mod 16)),(x -= 4 (mod 3)),(x -= 16 (mod 4)),(x -= 16 (mod 7)) :}$
che possiamo così riscrivere:
${ (x -= 4 (mod 16)),(x -= 1 (mod 3)),(x -= 0 (mod 4)),(x -= 2 (mod 7)) :}$.
Ora si vede che $x -= 4 (mod 16), x -= 0 (mod 4)$ è equivalente a $x -= 4 (mod 16)$.
Quindi il sistema è equivalente a:
${ (x -= 4 (mod 16)),(x -= 1 (mod 3)),(x -= 2 (mod 7)) :}$.
A questo punto poiché 16,3 e 7 sono coprimi, per il teorema cinese il sistema è equivalente a $x -= k (mod 16 times 3 times 7)$. Resta ora da trovare $k$: si procede per tentativi, cercandolo tra i numeri $4,20,36,52,68,84,100,116,132,148,164,180,196,212,228,244,260,276,292,308,324$ (che sono i numeri $-= 4 (mod 16)$ compresi tra $0$ e $336=16 times 3 times 7$)

[mistake89]

ho capito, grazie mille