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$

Grandad