0
$\begingroup$

The question is: solve $43^{159}$ mod $660$. I tried this one using Fermat Theorem, but it doesn't work since $660$ is not a prime. I also tried Euler's theorem, then I get a fact that $43^{\phi(660)}=43^{160} ≡ 1$ mod $660$, but I stuck at here! Can someone help me solve this question? Thanks!

$\endgroup$
2
$\begingroup$

Hint: use that $$43^4\equiv 1 \mod 660$$ and $$159=39\cdot 4+3$$

$\endgroup$
1
$\begingroup$

Since you know that $43^{160}\equiv 1$ and $43$ has an inverse (because it is coprime to $660$), you can multiply both sides by this inverse and conclude that $43^{159}\equiv 43^{-1}$.

To find the inverse you can use the Extended Euclidean Algorithm.

$\endgroup$
1
$\begingroup$

$$ \begin{align} 43^{159} % &\equiv 43^{1 + 2 + 4 + 8 + 16 + 128} \\ % &\equiv 43^1 \times 43^2 \times 43^4 \times 43^8 \times 43^{16} \times 43^{128} \\ % &\equiv 43 \times 529 \times 1 \times 1 \times 1 \times 1 \\ % &\equiv 307 & \pmod {660} % \end{align}$$

To compute $43^{2^{k+1}}$, first compute $43^{2^k}$ then square it and take the remainder mod 660.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.