Find all values of $n$ with $0 ≤ n ≤ 35$ such that the congruence $24x$ $≡$ $n$ $(mod$ $36)$ has a solution.

Question

I was checking the following number theory excercise:

Find all values of $n$ with $0 ≤ n ≤ 35$ such that the congruence $24x$ $≡$ $n$ $(mod$ $36)$ has a solution.

I made the $gcd$ between $12$ and $36$ and my conclusion was that the numbers are $12$ and $24$ but I think is not correct.

Any help will be really appreciated.

Answer 1

Take a look at the expression:

$c \equiv a \pmod b$

If $\gcd(a,b)=d \rightarrow \gcd(c,d) = d$

Since $24 = 2^3\cdot 3$ and $36 = 2^2\cdot 3^2$

Then $\gcd(24, 36) = 2^2\cdot 3 = 12$.

So the remainder has the form $12y$. How many $y's$ are there until $35$?

Right: $12\cdot 0, 12\cdot1$ and $12\cdot2=24$

Answer 2

$n$ has to be a multiple of $\operatorname{gcd}(24,36)=12$. So you left out $0$.