Find all the numbers that satisfy the congruences.

55 Views Asked by At

The problem is to find all the numbers in the interval [1,700000] that satisfy at the same time the congruences:

$ x\cong 1 (mod 5)$

$x^2 \cong 2 (mod 7)$

I know for example, that $x=11$ is one of this numbers, but I really don't know how to find the other solutions.

Thanks for any help.

1

There are 1 best solutions below

0
On

The pattern will recur every $5\cdot 7=35$, so you can just try them all. The first says only $1,6,11,16,21,26,31$ are candidates. I find one other. Then you can add any multiple of $35$ to these.