# Congruence, modular arithmetic

I am to show that from $$a \equiv 16^{12 \cdot18}(\bmod 247)$$, we have

1. $$a \equiv 8^{12 \cdot 18}(\bmod 247)$$
2. $$a \equiv 1(\bmod 247)$$

How do I proceed here? I tried at first using Fermat's little theorem, but I noticed that $$247$$ is not a prime, which is required. I'm therefore somewhat lost, and I would appreciate some help, tips, or something that can enlighten me.

We have not learned, and are not supposed to learn Euler's theorem in the course this exercise is taken from. I note that 247 is a Carmichael number, but we haven't really learned how to solve for those either. Are there any other ways to solve this?

• Use Euler's theorem. Notice that $\phi(247)=216=12\cdot18$.
– user799688
Oct 10 '20 at 11:47
• We have not learned, and are not supposed to learn Euler's theorem in the course this exercise is taken from. I note that $247$ is a Carmichael number, but we haven't really learned how to solve for those either. Are there any other ways to solve this? Oct 10 '20 at 14:55
• Well, you can calculate some stuff, but that is kinda painful. For example $16^2=256\equiv 9\pmod{247}$ and more stuff like this. To be honest, I won't do the calculating, but without Euler, there isnlt much more you can do.
– user799688
Oct 10 '20 at 16:19
• You know FLT but not Euler????? What about Chinese Remainder Theorem? Oct 10 '20 at 23:50
• Yes, just use CRT in these cases, as in splitting $247$ into prime factors to apply FLT, then synthesize with CRT.
– mpnm
Oct 12 '20 at 1:31

You have $$247 = 13 \cdot 19.$$ If you prove that $$13 \mid 16^{12\cdot 18} - 8^{12\cdot 18}$$, and $$19 \mid 16^{12\cdot 18} - 8^{12\cdot 18}$$, that will prove part a. You can use Fermat's Little Theorem for this.

After you work out the details, I don't think you'll have any trouble with part b.

First of all, $$247$$ is not a Carmichael number.

Second of all, use Fermat's little theorem with the prime factors of $$247=13\times19$$:

$$16^{12}\equiv1\bmod13$$, so $$16^{12\cdot18}\equiv1\bmod13$$, and $$16^{18}\equiv1\bmod19$$, so $$16^{12\cdot18}\equiv1\bmod19$$.

Then, as Bill Dubuque suggests, apply the constant case of the Chinese remainder theorem

to conclude that $$16^{12\cdot18}\equiv1\bmod247$$.

Hint:  since Euler phi is unknown, simply prove a two-prime case as below using little Fermat. Then the OP follows as special case $$\,p,q = 13,\,19,\,$$ $$\ N\! =\! (p\!-\!1)(q\!-\!1)\!=\! 12\cdot 18,\$$ $$\,a = 16,\,8$$.

Lemma $$\,\ \color{#c00}{p,q\nmid a},\,\ \color{#0a0}{p\!-\!1,q\!-\!1\mid N}\,\Rightarrow\, a^N\equiv 1\pmod{\!pq},\,$$ for $$\,\color{#90f}{{\rm primes}\ \,p\neq q}$$

Proof $$\,\bmod p\!:\ a^N = (\color{#c00}{a^{\large p-1}})^{\large \color{#0a0}{N/(p-1)}}\!\equiv \color{#c00}1^{\large \color{#0a0}K}\!\equiv 1\,$$ by little $$\rm\color{#c00}{Fermat}.\,$$ Similarly $$\,a^N\equiv 1\pmod{\!q},\,$$ $$\rm\color{#90f}{hence}$$ $$\,a^{N}\equiv 1\pmod{\!pq}\,$$ by LCM or CCRT = Constant-case CRT.

Remark $$\,$$ Above we used basic congruence arithmetic rules, notably $$\,b\equiv c\Rightarrow\, b^k\equiv c^k,\,$$ the Congruence Power Rule.

Since the proof works for any expt $$N$$ that is a common multiple of $$\,p\!-\!1,\,q\!-\!1\,$$ it also works for $$N =$$ LCM = least common multiple $$= [p\!-\!1,q\!-\!1] = [12,18] = 6[2,3] = 36\,$$ or any multiple.

When you learn Euler's totient (phi) theorem you may note that as above we can also use LCM to reduce the exponents, a generalization known Carmichael's Lambda Theorem.