How do I find the value of this unknown in the congruence relation mod a non-prime?

325 Views Asked by At

Solve for $x$ where $77x \equiv 11 \pmod {40}$. I have tried to factor 40 into primes, which gives me 2 and 5, and tried to use the chinese remainder theorem to get the factors. However, I don't think i can really use CRT since the 2 will be repeated (2^3, repeating the factors 2 three times).

Also, solving for x halfway, I found out that x must be even, but I'm unable to make use of the information that 7 and 11 are prime.

1

There are 1 best solutions below

0
On BEST ANSWER

You might solve it mod $8$ and mod $5$, then use CRT. $5$ and $8$ are small enough that you can do those by hand.

You might also note that $11$ is coprime to $40$, so you can start by dividing both sides by $11$, making the equation $7x \equiv 1 (\text{mod } 40)$.