2
$\begingroup$

I want to simplify the expression \begin{align} 26! \cdot x \equiv 730^{171} \pmod{232} \end{align} My first step is to solve for $26! \cdot a \equiv 1 \pmod{232}$, that is, find the inverse of $26!$ modulo $232$.
To simplify, I should first calculate $26! \bmod{232}$. Using Wilson's theorem seems to be the best approach. But since $232 = 2^3 \cdot 29$ is not a prime number, I have to split up the expression using the Chinese Remainder Theorem: \begin{align*} \begin{cases} 26! \equiv a \pmod{29}\\ 26! \equiv b \pmod{8} \end{cases} \end{align*} I can use Wilsons theorem to solve the first equation as follows: \begin{align*} 28! = 26!\cdot 27 \cdot 28 \equiv 26!(-2)(-1) \equiv 26!\cdot 2 \equiv -1 \pmod{29} \end{align*} Using that $2\cdot 15 \equiv 1 \pmod{29}$, we find \begin{align*} 26! \equiv -15 \equiv 14 \pmod{29} \end{align*} However, I cannot use Wilsons theorem to solve the second equation. Any suggestions on how to solve that? Or might there be a better way to calculate $26! \bmod{232}$ altoghether?

$\endgroup$
  • $\begingroup$ well $26! \equiv 0 \pmod{8}$ $\endgroup$ – user159517 Oct 23 '16 at 13:41
  • $\begingroup$ How do you know that $26! \equiv 0 \pmod{8}$? $\endgroup$ – SBS Oct 23 '16 at 14:01
  • $\begingroup$ because $n!$ is a multiple of $k$ for $k < n$... $\endgroup$ – user159517 Oct 23 '16 at 14:12
  • $\begingroup$ $26!$ is not invertible modulo $232$, as these numbers are not relatively prime (they contain a factor of $2$ in common). $\endgroup$ – theyaoster Oct 23 '16 at 15:56
2
$\begingroup$

Hint: Divide by $2^3$ on both sides (and the modulus) to obtain the equivalent congruence: $$(26)(25)(3)(23!) x \equiv (365)^3(730)^{168} \pmod{29}$$

Note that the left side contains $(26)(25)(3)(23!)$, which is relatively prime to $29$ and thus invertible modulo $29$ (like in the work you have done, Wilson's Theorem can be useful here). Then note that $730$ and $29$ are relatively prime; this permits you to use Fermat's Little Theorem (or Euler's Theorem) to simplify $730^{168}$.

It should be more straightforward from there.

$\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.