1

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?

Ankit
  • 13

3 Answers3

2

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}$$

DanielV
  • 23,556
0

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.)

ET93
  • 1,226
  • How do we reduce this value of x down to < 400? We don't know what multiple of 400 to subtract. – Ankit Oct 24 '14 at 14:19
  • We can subtract any multiple of 400 since 400=0 mod 400. So after you find a solution x. Reduce by whatever multiple of 400 required. Just dividing x by 400 and taking the remainder will work as well. – ET93 Oct 24 '14 at 14:20
  • It's hard to perform divisions on such a large number. Is it possible to directly reduce the power and then keep subtracting 400. – Ankit Oct 24 '14 at 14:23
0

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}\;$

Timbuc
  • 34,191