1. ## congruency questions

Find all integers $x$ with $0\leq x\leq621$which are the solutions of $255x\equiv12(mod621)
$

I got the gcd(255,621) to be 3.

And my linear congruency was 3=621*23+255*(-56)

But i am not sure on how solve the for all values.

2. Hello cooltowns
Originally Posted by cooltowns
Find all integers $x$ with $0\leq x\leq621$which are the solutions of $255x\equiv12(mod621)
$

I got the gcd(255,621) to be 3.

And my linear congruency was 3=621*23+255*(-56)

But i am not sure on how solve the for all values.
OK, so you can now say:
$255\times(-56) = 621\times(-23)+3$

$\Rightarrow 255\times(-56) \equiv3\mod621$

$\Rightarrow 255\times(-224) \equiv12\mod621$
We now note that $255=85\times3$ and $621=207\times3$.
$\Rightarrow 85\times3(-224+207n)\equiv12\mod621, n = 1, 2, 3, ...$
So the general solution of
$255x\equiv12\mod621$
is
$x=-224+207n$
And in particular, taking $n = 2, 3, 4$, we get the solutions for $0\le x< 621$:
$x = 190, 397, 604$