Sistema di congruenze senza teorema cinese del resto.
Buongiorno a tutti,
ho il seguente sistema di congruenze lineari:
${(13x -= 32 (mod 99)),(13x -= 14 (mod 21)):}$
scrivo qui i passaggi che ho fatto per la risoluzione, ma non credo siano corretti
e spero in un vostro supporto per farvore.
innanzi tutto $MCD(21,99) != 1$ quindi Teorema cinese del resto non applicabile in questo caso.
Risolvo la prima:
$99 = 13*7+8$
$8x -= -7 * 32 (mod 99)$
$8x -= -224 (mod 99)$
$8x -= 73 (mod 99)$
$99 = 8*12+3$
$3x -= -12 * 73 (mod 99)$
$3x -= -876 (mod 99)$
$3x -= 15 (mod 99)$
$MCD(3,99) = 3$ divido tutto per 3
$x -= 5 (mod 33)$
$x = 5 + 33k$
il valore ottenuto lo vado a sostituire nella seconda:
$13(5+33y) -= 14 (mod 21)$
$65 + 429y -= 14 (mod 21)$
$429y -= 14 - 65 (mod 21)$
$429y -= -51 (mod 21)$
$429y -= 12 (mod 21)$
$143y -= 4 (mod 7)$
$3y -= 4 (mod 7)$
$7 = 3*2+1$
$y -= -2 + 4 (mod 7)$
$y -= 2 (mod 7)$
$y = 2 + 7k$
ma non credo sia corretto
mi sa che ho sbagliato qualcosa nel sostituire il risultato della prima nella seconda
spero in un vostro supporto.
grazie a tutti.
ho il seguente sistema di congruenze lineari:
${(13x -= 32 (mod 99)),(13x -= 14 (mod 21)):}$
scrivo qui i passaggi che ho fatto per la risoluzione, ma non credo siano corretti
e spero in un vostro supporto per farvore.
innanzi tutto $MCD(21,99) != 1$ quindi Teorema cinese del resto non applicabile in questo caso.
Risolvo la prima:
$99 = 13*7+8$
$8x -= -7 * 32 (mod 99)$
$8x -= -224 (mod 99)$
$8x -= 73 (mod 99)$
$99 = 8*12+3$
$3x -= -12 * 73 (mod 99)$
$3x -= -876 (mod 99)$
$3x -= 15 (mod 99)$
$MCD(3,99) = 3$ divido tutto per 3
$x -= 5 (mod 33)$
$x = 5 + 33k$
il valore ottenuto lo vado a sostituire nella seconda:
$13(5+33y) -= 14 (mod 21)$
$65 + 429y -= 14 (mod 21)$
$429y -= 14 - 65 (mod 21)$
$429y -= -51 (mod 21)$
$429y -= 12 (mod 21)$
$143y -= 4 (mod 7)$
$3y -= 4 (mod 7)$
$7 = 3*2+1$
$y -= -2 + 4 (mod 7)$
$y -= 2 (mod 7)$
$y = 2 + 7k$
ma non credo sia corretto
mi sa che ho sbagliato qualcosa nel sostituire il risultato della prima nella seconda
spero in un vostro supporto.
grazie a tutti.
Risposte
ne posto un altro:
${(x -= 225 (mod 250)),(x -= 150 (mod 1225)):}$
la prima è $x = 225 + 250y$
sostituisco nella seconda:
$225+250y -= 150 (mod 1225)$
$250y -= 150 - 225 (mod 1225)$
$250y -= -75 (mod 1225)$
$250y -= 1150 (mod 1225)$ <-- divido per 25 e ottengo la seguente
$10y -= 46 (mod 49)$ <-- poichè $MCD (10,49) = 1$ divido per 2 e ottengo la seguente
$5y -= 23 (mod 49)$
$49 = 5*9+4$
$4y -= -9 + 23 (mod 49)$
$4y -= 14 (mod 49)$ <-- poichè $MCD (4,49) = 1$ divido per 2 e ottengo la seguente
$2x -= 7 (mod 49)$
$49 = 2*24+1$
$y -= -24+7 (mod 49)$
$y -= -17 (mod 49)$
$y -= 32 (mod 49)$
ma anche questo non esce il risultato dovrebbe essere $y -= 34 (mod 49)$
forse perchè avevo diviso per 2 prima?, o forse perchè ho diviso per 25 prima?
P.S. le modifiche effettuate al post riguardano l'aggiunta di dettagli per una migliore lettura dei passaggi.
${(x -= 225 (mod 250)),(x -= 150 (mod 1225)):}$
la prima è $x = 225 + 250y$
sostituisco nella seconda:
$225+250y -= 150 (mod 1225)$
$250y -= 150 - 225 (mod 1225)$
$250y -= -75 (mod 1225)$
$250y -= 1150 (mod 1225)$ <-- divido per 25 e ottengo la seguente
$10y -= 46 (mod 49)$ <-- poichè $MCD (10,49) = 1$ divido per 2 e ottengo la seguente
$5y -= 23 (mod 49)$
$49 = 5*9+4$
$4y -= -9 + 23 (mod 49)$
$4y -= 14 (mod 49)$ <-- poichè $MCD (4,49) = 1$ divido per 2 e ottengo la seguente
$2x -= 7 (mod 49)$
$49 = 2*24+1$
$y -= -24+7 (mod 49)$
$y -= -17 (mod 49)$
$y -= 32 (mod 49)$
ma anche questo non esce il risultato dovrebbe essere $y -= 34 (mod 49)$
forse perchè avevo diviso per 2 prima?, o forse perchè ho diviso per 25 prima?
P.S. le modifiche effettuate al post riguardano l'aggiunta di dettagli per una migliore lettura dei passaggi.
l'errore nel secondo sistema dovrebbe essere intorno a $4y -= 14 (mod 49)$ ma non riesco a risolverlo.
Bentrovato!
Ti propongo come l'avrei risolto io! La prima equazione è: (io scrivo tra parentesi il mod, sottointendendolo)
[tex]13x\equiv 32 (99)[/tex]
[tex]x\equiv 13^{-1}32 (99)[/tex]
che si risolve ricordando qualche conto e che [tex]1=5 \cdot 99 - 38 \cdot 13[/tex]:
[tex]x\equiv 13^{-1}\cdot 32 (99)[/tex]
[tex]x\equiv 38 \cdot 32 (99)[/tex]
[tex]x\equiv 1216 (99)[/tex]
[tex]x\equiv 28 (99)[/tex]
Da qui calcolo sull'altra con [tex]x = 28 + t \cdot 99[/tex]
[tex]13 (28 + t \cdot 99) \equiv 14 (21)[/tex]
[tex]13 (7 + t \cdot 15) \equiv 14 (21)[/tex]
[tex]15t \equiv (13^{-1} \cdot 14 - 7)(21)[/tex]
Ora sappiamo che:
[tex]21 \cdot 5 - 13 \cdot 8=1[/tex]
quindi:
[tex]15t \equiv (8 \cdot 14 - 7)(21)[/tex]
[tex]15t \equiv 105 (21)[/tex]
[tex]15t \equiv 0 (21)[/tex]
[tex]t \equiv 0 (7)[/tex]
ed allora la soluzione generale è:
[tex]x = 28 + 99 \cdot 7 \cdot k[/tex]
Ti propongo come l'avrei risolto io! La prima equazione è: (io scrivo tra parentesi il mod, sottointendendolo)
[tex]13x\equiv 32 (99)[/tex]
[tex]x\equiv 13^{-1}32 (99)[/tex]
che si risolve ricordando qualche conto e che [tex]1=5 \cdot 99 - 38 \cdot 13[/tex]:
[tex]x\equiv 13^{-1}\cdot 32 (99)[/tex]
[tex]x\equiv 38 \cdot 32 (99)[/tex]
[tex]x\equiv 1216 (99)[/tex]
[tex]x\equiv 28 (99)[/tex]
Da qui calcolo sull'altra con [tex]x = 28 + t \cdot 99[/tex]
[tex]13 (28 + t \cdot 99) \equiv 14 (21)[/tex]
[tex]13 (7 + t \cdot 15) \equiv 14 (21)[/tex]
[tex]15t \equiv (13^{-1} \cdot 14 - 7)(21)[/tex]
Ora sappiamo che:
[tex]21 \cdot 5 - 13 \cdot 8=1[/tex]
quindi:
[tex]15t \equiv (8 \cdot 14 - 7)(21)[/tex]
[tex]15t \equiv 105 (21)[/tex]
[tex]15t \equiv 0 (21)[/tex]
[tex]t \equiv 0 (7)[/tex]
ed allora la soluzione generale è:
[tex]x = 28 + 99 \cdot 7 \cdot k[/tex]
Dalla seconda equazione:
[tex]x\equiv 150(1225)[/tex]
[tex]x=150 + 1225t[/tex]
che inserisco nella prima:
[tex]x\equiv 225(250)[/tex]
[tex]150 + 1225 t \equiv 225(250)[/tex]
[tex]-25 t \equiv 75(250)[/tex]
Da cui non potendo cercare direttamente l'inverso, osservo che mi posso ridurre dividendo tutto per [tex]25[/tex] a:
[tex]-t \equiv 3(10)[/tex]
[tex]t \equiv 7(10)[/tex]
e quindi la soluzione è:
[tex]x = 150 + (7+10k)\cdot 1225[/tex]
[tex]x = 8725 + 12250k[/tex]
[tex]x\equiv 150(1225)[/tex]
[tex]x=150 + 1225t[/tex]
che inserisco nella prima:
[tex]x\equiv 225(250)[/tex]
[tex]150 + 1225 t \equiv 225(250)[/tex]
[tex]-25 t \equiv 75(250)[/tex]
Da cui non potendo cercare direttamente l'inverso, osservo che mi posso ridurre dividendo tutto per [tex]25[/tex] a:
[tex]-t \equiv 3(10)[/tex]
[tex]t \equiv 7(10)[/tex]
e quindi la soluzione è:
[tex]x = 150 + (7+10k)\cdot 1225[/tex]
[tex]x = 8725 + 12250k[/tex]
praticamente nella prima equazione ti ricavi l'identità di bezout.
è un po' oneroso come procedimento o no?
lo dico perchè io faccio questi passaggi:
considero $13x - 99y = 32$
trovo MCD con Euclide:
$99 = 13*7+8$
$13=8*1+5$
$8=5*1+3$
$5=3*1+2$
$3=2*1+1$
$2=1*2+0$
$MCD(99,13) = 1$
isolo i resti:
$8=99-13*7$
$5=13-8*1$
$3=8-5*1$
$2=5-3*1$
$1=3-2*1$
esprimo $1$ nella forma $\alpha a + \beta b$
e alla coppia $a$ e $b$ associo rispettivamente $(1,0)$ e $(0,1)$
$8=a+b(-7) = (1,0)+(0,1)(-7) -= $
$-= (1,0) + (0,-7) -=$
$-= (1,-7)$
$5=(0,1)+(1,-7)(-1) -=$
$-= (0,1)+(-1,7)$ -=$
$-= (-1,8)$
$3 = (1,-7)+(-1,8)(-1) -=$
$-= (1,-7)+(1,-8) -=$
$-= (2,-15)$
$2 = (1,8)+(2,-15)(-1) -=$
$-= (-1,8)+(-2,15) -=$
$-= (-3,23)$
$1 = (2,-15)+(-3,23)(-1) -=$
$-= (2, -15)+ (3,-23) -=$
$-= (5, -38)$
sostituisco nella relazione
$\alpha a + \beta b = (\alpha, \beta)$
$5*99+(-38)13 -= (5,-38)$
$5*99+(-38)13 -= 1$
moltiplico per $32$ considerando il termine noto dell'equazione considerata:
$(32)(5)99 + (32)(-38)13 = 32$
$(160)99 + (-1216)13 = 32$
ottengo:
$x = x_0 + kb \Rightarrow x= -1216 + 99k$
$y = y_0 - ka \Rightarrow y = 160 - 13k$
la prima quindi diventa:
$x -= -28 (mod 99)$
$x -= 71 (mod 99)$
$x = 71 + 99k$
che andrò a sostituire nella seconda
della $y$ non ne faccio niente?
quindi dovrebbe essere quella esatta $x = 71 + 99k$ e non $x = 28 + 99k$, come è stato scritto nel post precedente da Lord K, o sbaglio?
ed inoltre perchè con questo procedimento è uscito bene mentre con l'altro che ho postato all'inizio ottengo un risultato diverso, cioè $y = 5+33k$? potreste dirmi per favore dove ho sbagliato, così da comprenderlo e cercare di non ripetere in futuro lo stesso errore?
forse per il fatto che nella prima ho diviso tutto per 3?
è un po' oneroso come procedimento o no?
lo dico perchè io faccio questi passaggi:
considero $13x - 99y = 32$
trovo MCD con Euclide:
$99 = 13*7+8$
$13=8*1+5$
$8=5*1+3$
$5=3*1+2$
$3=2*1+1$
$2=1*2+0$
$MCD(99,13) = 1$
isolo i resti:
$8=99-13*7$
$5=13-8*1$
$3=8-5*1$
$2=5-3*1$
$1=3-2*1$
esprimo $1$ nella forma $\alpha a + \beta b$
e alla coppia $a$ e $b$ associo rispettivamente $(1,0)$ e $(0,1)$
$8=a+b(-7) = (1,0)+(0,1)(-7) -= $
$-= (1,0) + (0,-7) -=$
$-= (1,-7)$
$5=(0,1)+(1,-7)(-1) -=$
$-= (0,1)+(-1,7)$ -=$
$-= (-1,8)$
$3 = (1,-7)+(-1,8)(-1) -=$
$-= (1,-7)+(1,-8) -=$
$-= (2,-15)$
$2 = (1,8)+(2,-15)(-1) -=$
$-= (-1,8)+(-2,15) -=$
$-= (-3,23)$
$1 = (2,-15)+(-3,23)(-1) -=$
$-= (2, -15)+ (3,-23) -=$
$-= (5, -38)$
sostituisco nella relazione
$\alpha a + \beta b = (\alpha, \beta)$
$5*99+(-38)13 -= (5,-38)$
$5*99+(-38)13 -= 1$
moltiplico per $32$ considerando il termine noto dell'equazione considerata:
$(32)(5)99 + (32)(-38)13 = 32$
$(160)99 + (-1216)13 = 32$
ottengo:
$x = x_0 + kb \Rightarrow x= -1216 + 99k$
$y = y_0 - ka \Rightarrow y = 160 - 13k$
la prima quindi diventa:
$x -= -28 (mod 99)$
$x -= 71 (mod 99)$
$x = 71 + 99k$
che andrò a sostituire nella seconda
della $y$ non ne faccio niente?
quindi dovrebbe essere quella esatta $x = 71 + 99k$ e non $x = 28 + 99k$, come è stato scritto nel post precedente da Lord K, o sbaglio?
ed inoltre perchè con questo procedimento è uscito bene mentre con l'altro che ho postato all'inizio ottengo un risultato diverso, cioè $y = 5+33k$? potreste dirmi per favore dove ho sbagliato, così da comprenderlo e cercare di non ripetere in futuro lo stesso errore?
forse per il fatto che nella prima ho diviso tutto per 3?
continuo.
vado a sostituire $x=71+99k$ nella seconda congruenza e ottengo:
$13(71+99k) -= 14 (mod 21)$
$923 + 1287k -= 14 (mod 21)$
$1287k -= 14 - 923 (mod 21)$
$1287k -= -909 (mod 21)$
$1287k -= 15 (mod 21)$
nella precedente divido tutto per 3:
$429k -= 5 (mod 7)$
riduco modulo 7
$2k -= 5 (mod 7)$
procedimento 1
a questo punto se faccio tramite il mio procedimento che ho utilizzato all'inizio, non esce il risultato sperato. e cioè:
$2k -= 5 (mod 7)$
$7 -= 2*3+1$
$k -= -3+5 (mod 7)$
$k -= 2 (mod 7)$
$k -= 2 + 7t$
procedimento 2
invece se applico il procedimento con l'identità di Bezout esce correttamente:
$2k -= 5 (mod 7)$
$2x - 7y = 5$
trovo $MCD(7,2)$ tramite Euclide
$7 = 2*3+1$
$2=1*2+0$
quindi $MCD(7,2) = 1$.
isolo i resti:
$1 = 7-2*3$
procedo come prima:
$1 = (1,0)+(0,1)(-3) -=$
$-= (1,0)+(0,-3) -=$
$-= (1,-3)$
$\alpha a + \beta b -= (\alpha + \beta) \Rightarrow$
$(1)7 + (-3)2 = 1$
moltiplico per 5
$5(1)7 + 5(-3)2 = 1$
$x = x_0 + kb \Rightarrow x = -15 - 7b \Rightarrow x -= 6 (mod 7)$
$y = y_0 - ka \Rightarrow y = 5 - 2k$
in effetti il risultato $x -= 6 (mod 7)$ è corretto!!
ma perchè con l'altro mio procedimento non esce?
se poi vado a sostituire nella soluzione della prima congruenza:
$x = 71+99(6 + 7t)$
$x = 71+594+693t$
$x=665+693t$
$x -= 665 (mod 693)$ che è il risultato sperato!!
ma perchè con il mio procedimento non esce?
tante volte questo con Bezout sembra molto oneroso, ecco perchè preferirei utilizzare l'altro mio metodo...
vado a sostituire $x=71+99k$ nella seconda congruenza e ottengo:
$13(71+99k) -= 14 (mod 21)$
$923 + 1287k -= 14 (mod 21)$
$1287k -= 14 - 923 (mod 21)$
$1287k -= -909 (mod 21)$
$1287k -= 15 (mod 21)$
nella precedente divido tutto per 3:
$429k -= 5 (mod 7)$
riduco modulo 7
$2k -= 5 (mod 7)$
procedimento 1
a questo punto se faccio tramite il mio procedimento che ho utilizzato all'inizio, non esce il risultato sperato. e cioè:
$2k -= 5 (mod 7)$
$7 -= 2*3+1$
$k -= -3+5 (mod 7)$
$k -= 2 (mod 7)$
$k -= 2 + 7t$
procedimento 2
invece se applico il procedimento con l'identità di Bezout esce correttamente:
$2k -= 5 (mod 7)$
$2x - 7y = 5$
trovo $MCD(7,2)$ tramite Euclide
$7 = 2*3+1$
$2=1*2+0$
quindi $MCD(7,2) = 1$.
isolo i resti:
$1 = 7-2*3$
procedo come prima:
$1 = (1,0)+(0,1)(-3) -=$
$-= (1,0)+(0,-3) -=$
$-= (1,-3)$
$\alpha a + \beta b -= (\alpha + \beta) \Rightarrow$
$(1)7 + (-3)2 = 1$
moltiplico per 5
$5(1)7 + 5(-3)2 = 1$
$x = x_0 + kb \Rightarrow x = -15 - 7b \Rightarrow x -= 6 (mod 7)$
$y = y_0 - ka \Rightarrow y = 5 - 2k$
in effetti il risultato $x -= 6 (mod 7)$ è corretto!!
ma perchè con l'altro mio procedimento non esce?
se poi vado a sostituire nella soluzione della prima congruenza:
$x = 71+99(6 + 7t)$
$x = 71+594+693t$
$x=665+693t$
$x -= 665 (mod 693)$ che è il risultato sperato!!
ma perchè con il mio procedimento non esce?
tante volte questo con Bezout sembra molto oneroso, ecco perchè preferirei utilizzare l'altro mio metodo...
mi è chiaro il procedimento di Lord K per il secondo sistema. Ma non riesco a capire cosa ci sia di sbagliato nel mio.
"bla99hf":
$5y -= 23 (mod 49)$
$49 = 5*9+4$
$4y -= -9 + 23 (mod 49)$
L'errore del tuo metodo è qui, infatti non si può fare la sostituzione in questo modo, [tex]49=5\cdot 9 + 4[/tex] da cui [tex]0\equiv 5\cdot 9 + 4(49)[/tex], nell'uguaglianza che abbiamo:
[tex]5y \equiv 23 (49)[/tex]
[tex]9\cdot 5y \equiv 9\cdot 23 (49)[/tex]
[tex]-4y \equiv 9\cdot 23 (49)[/tex]
Che è ben differente da quello che trovi tu.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo