Cryptology number theory

Question

By using Chinese Remainder Theorem, how many solutions are there to $b^{1104} = 1 \pmod{5*13*17}$ with $gcd(b, 1105) = 1$?

Answer 1

Recall that a composite $n$ is a Carmichael number if for any $b$ relatively prime to $n$, $b^{n−1} \equiv 1 \pmod n$.

We want to show that $1105$ is a Carmichael number.

You are given a hint: $1105 = 5 \cdot 13 \cdot 17$.

We want to show that if $b$ is relatively prime to $1105$, then $b^{1104} \equiv 1 \pmod {1105}$.

By the Chinese Remainder Theorem, it suffices to show that:

• $b^{1104} \equiv 1 \pmod {5}$,
• $b^{1104} \equiv 1 \pmod {13}$, and
• $b^{1104} \equiv 1 \pmod {17}$.

By Fermat’s Little Theorem, $a^{p−1} \equiv 1 \pmod p$ if $a$ is relatively prime to $p$.

We are given that $\gcd(b, 1105) = 1$, that is, $b$ is relatively prime to $1105$, so $b$ is also relatively prime to $5, 13$, and $17$. Thus

• $b^{4} \equiv 1 \pmod {5}$,
• $b^{12} \equiv 1 \pmod {13}$, and
• $b^{16} \equiv 1 \pmod {17}$.

Thus, $b^{4n} ≡ 1 \pmod {5}$ for all $n$; similarly $b^{12n} \equiv 1 \pmod {13}$ and $b^{16n} \equiv 1 \pmod {17}$ for all $n$.

Since $4, 12$, and $16$ all divide $1104$ evenly, that is $\{276, 92, 69\}$ times, it follows that:

• $b^{1104} \equiv 1 \pmod {5}$,
• $b^{1104} \equiv 1 \pmod {13}$, and
• $b^{1104} \equiv 1 \pmod {17}$.

Thus, $n = 4 \cdot 12 \cdot 16 = 768$ (know what those are from (the analysis above should tell you).

Answer 2

Using Carmichael Function, $\lambda(1104)=$lcm$(4,12,16)=48$

$\implies b^{48}\equiv1\pmod{5\cdot13\cdot17}$

Now, $1104\equiv0\pmod {48}\implies b^{1104}\equiv1\pmod{5\cdot13\cdot17}$ for any integer $b$ co-prime with $5\cdot13\cdot17$

The number such $b$ is $\phi(5\cdot13\cdot17)=\phi(5)\cdot\phi(13)\cdot\phi(17)$

Answer 3

Hint $\ $ Distinct primes $\rm\ p,q,r\nmid b\ $ and $\rm\:p\!-\!1,q\!-\!1,r\!-\!1\mid n\:\!\stackrel{Fermat}\Rightarrow p,q,r\mid b^n\!-\!1\stackrel{Euler}\Rightarrow pqr\mid b^n\!-\!1 $