How the find the smallest positive solution of $353x\equiv 254\mod 400$?

Question

The method that I'm trying to follow is that x = 254 x 353$^{\phi(400)-1}$ where $\phi$ is the Euler's totient function. But how do we find the lowest possible solution?

Answer 1

Since $\operatorname{GCD}(353, 400) = 1$, the modular inverse of $353 \pmod {400}$ exists and is unique, and so $x \equiv 254 \times 353^{-1} \pmod {400}$ is unique.

The common approach to finding the modular inverse is to use the Extended Eucliean Algorithm, but according to wikipedia, if you know the factorization of the modular base then Euler's totient function is feasible as well.

$$\phi(m) = m \prod_{p|m, ~~p \in \text{prime}} \left(1 - \frac 1p\right)$$ $$m = 400 = 2^45^2$$

So

$$\phi(400) = 400\left(1 - \frac 12\right)\left(1 - \frac 15\right) = 160$$

Since

$$a^{-1} \equiv a^{\phi(m) - 1} \pmod m$$

We have

$$353^{-1} \equiv 353^{159} \equiv 17 \pmod {400}$$

By modular exponentiation. So what is left is to find

$$x \equiv 353^{-1} \times 254 \equiv 17 \times 254 \equiv \boxed{318} \pmod {400}$$

Answer 2

We are working mod 400 so the lowest possible positive solution is one between 1 and 400. If you get a solution out of that range, you can add or subtract 400. Also, to use this method, you should check that 353 (or -47 mod 400) and 400 are relatively prime. Finally, we would have mod 400, $$353^{\phi(400)}=1$$$$353*353^{\phi(400)-1}=1$$ So $$x=254*353^{\phi(400)-1}$$ (I think it is easier to use the Division Algorithm to find the inverse of 353 mod 400 which is what we are doing here.)

Answer 3

Some ideas to make things easier...or at least less difficult...probably:

$$\begin{align*}&400 = 1\cdot 353+47\\ &353=7\cdot47+24\\ &47=1\cdot24+23\\ &24=1\cdot23+1\\ &23=23\cdot1\end{align*}$$

and from here

$$1=24-23=24-(47-24)=2\cdot24-47=2(353-7\cdot47)-47=$$

$$=2\cdot353-15\cdot47=2\cdot353-15(400-353)=17\cdot353-15\cdot400$$

and from here $\;353^{-1}=17\pmod{400}\;$