Domanda sulla congruenza lineare

[valerimartohan]

Determinare il numero di soluzioni tale che 500<= x <= 600

della seguente congruenza

450 x congruo 180 mod(840)

Io ho trovato una soluzione che corrisponde a x = 762, ma è esclusa dal campo

Le alternative sono

A 6
B 7
C 4
D 5

Dove è l'errore? Grazie!

[ghira1]

"valerimartohan":
Dove è l'errore? Grazie!

Quale errore?

[Gi81]

Riscrivo il testo in maniera più comprensibile:

Determinare il numero di soluzioni di $450 x -= 180 (mod 840)$ tali che $500<= x <= 600$

Perdonami, ma come possiamo farti capire dove sia l'errore, se non hai messo il procedimento che hai seguito?
Ad esempio:

"valerimartohan":Io ho trovato una soluzione che corrisponde a x = 762, ma è esclusa dal campo

Come hai trovato questa soluzione?

[ghira1]

Proviamo con la forza bruta:

#!/usr/bin/perl

for (500..600) {
if (450*$_%840 == 180) {
print "$_\n";
}
}

ghira@salotto2022:~$ perl cong.p
510
538
566
594

[valerimartohan]

Ho trovato il risultato con identità di Bezout ed MCD

MCD (450, 840) = 30

30 = (7)(840) + (-13)(450)

Moltiplico -13 per 6 ed ottengo -78, sommo il modulo 840 e ottengo 762.

I risultati generici sono 762 + 28k, con k interi Z. E cosí posso risalire ai risultati compresi tra 500 e 600, è un metodo corretto?

Grazie mille per vostre risposte!

[Gi81]

Sì, direi proprio che hai scritto i passaggi corretti.
Quando ottieni $-78$, lo puoi sommare già modulo $28$, ottenendo $6$.

Quindi i risultati generici sono $6+28k$, con $k in ZZ$.

[Gi81]

Io ho fatto così, per risolvere l'equazione:
L'equazione iniziale è equivalente a $15x-=6 (mod 28)$ (perchè?)
che è equivalente a $5x-=2 (mod 28)$ (perché?)

Dato che $28=4*7$, possiamo trasformare l'equazione in ${(5x-=2 mod4),(5x-=2 mod7):}=>$
$=> {(x-=2 mod4),(5x -= -5 mod7):} => {(x-=2 mod4),(x-= -1 mod7):} => x-= 6 (mod 28)$