1. congruency questions

Find all integers $\displaystyle x$ with $\displaystyle 0\leq x\leq621$which are the solutions of $\displaystyle 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 $\displaystyle x$ with $\displaystyle 0\leq x\leq621$which are the solutions of $\displaystyle 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:
$\displaystyle 255\times(-56) = 621\times(-23)+3$

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

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