How to find all solutions using Euclidean Algorithm for Congruence

Question

I have 10x = 5 (mod 35)

Using cancellation rules I have changed this to 2x=1 (mod 7)

I then used Euclidean Algorithm to get x = -3 (2x+7y = 5 when x=-3 and y=1)

How do I know convert this to a general rule (ie -3n + something or n-3?)

Answer 1

You are correct in having found one solution: $x \equiv -3$.

Given $x\equiv -3\mod 7$, then $$x\equiv -3 \pm 7k,\quad k\in \mathbb Z$$ So, for example, you could alternatively conclude

$x \equiv 4 \mod 7$,

since $-3 + (1)(7) = 4.$

Indeed, $$x\in \{ ...-10, -3, 4, 11,...\}$$

Answer 2

Rewrite $2x \equiv 1 \pmod 7$ as $2x \equiv 8 \pmod 7$. Now cancel (multiply by the inverse of $2$) to give $x \equiv 4 \pmod 7$.