0
$\begingroup$

The system is given as:$$ \begin{matrix}x \equiv _{107} 52!53! \\ x \equiv _{16} 11^{9^{13}}\end{matrix}$$

$gcd(16, 107) = 1$ so Chinese remainder theorem can be applied. However, my issue are the factorials, I don't know how to solve that one. (I think Wilson's theorem can be used but I am inexperienced with it and would seek a different route)

As for$x \equiv _{16} 11^{9^{13}}$,$11 \equiv _{16} -5$ and also$gcd(11, 16) = 1$ so Euler's totient function can be applied:

$\phi(16) = \phi(2^4) = 2^4 - 2^3 = 8$

$9^{13} \equiv _8 ?$ I know that$9\equiv _8 1$ and$gcd(13, 8) = 1$, Euler again:

$\phi(8) = \phi(2^3) = 2^3 - 2^2 = 4$ and finally$13\equiv _4 1$.

Puting it back together$(-5)^{1^1} \equiv _{16} 11$.

Can anyone help me with factorial and the rest of the CRT?

askedOct 8 at 20:47
Danilo Jonić's user avatar
$\endgroup$
9
  • $\begingroup$Is it important to do it by hand? If not, iterated multiplication $\pmod {107}$ isn't difficult.$\endgroup$CommentedOct 8 at 20:54
  • $\begingroup$Have you considered usingWilson's theorem, as well as that $p-n\equiv -n\pmod{p}$ (e.g., for $1\le n\le\frac{p-1}{2}$ for odd integers, including primes, $p$, such as $107$)?$\endgroup$CommentedOct 8 at 20:57
  • $\begingroup$Hint: $52!$ is also the product of $ -1, -2,\dots,-52$. As the multiplicative group of the numbers modulo 107 is cyclic, $n^2\equiv 1$ modulo 107 iff $n$ is congruent to -1 modulo 107. Thus, $106!$ is congruent to $-1$ modulo 107 (as each element is multiplied by its inverse). Now combine these two facts.$\endgroup$CommentedOct 8 at 20:58
  • 1
    $\begingroup$FWIW, $52!53! \equiv 105 \pmod{107}$ and $11^{9^{13}} \bmod 16 \equiv 11 \pmod{16}$. Combining the two equations gives $x \equiv 747 \pmod{1712}$. But I “cheated” by using a computer.$\endgroup$CommentedOct 8 at 21:26
  • 1
    $\begingroup$@JohnOmielan Very nice comment. I did intend that the answer would be $~(-1) \times 54^{-1},~$ but it never occurred to me that this equals $~(-54)^{-1}.$$\endgroup$CommentedOct 9 at 2:13

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.