Evaluate $6^{433} \pmod {21}$ and a proving question

Question

Question 1:
Denote $a \mod b$ as $a \% b$, where $a$ and $b$ are some integers

Evaluate 12^32475 % 21 

The following is what I tried:

12^32475 % 21 = (12^3 % 21)^10825 % 21 = 6^10825 % 21 = ... = 6^433 % 21

But how to continue ?

Question 2:

I don't understand this: n-1= -1 mod n. Where is this from? And does this line become the next line?

Context: my class is discrete math for computer science. So far for related topics, it covers modular inverse, (extended) GCD algorithm, Fermat's Little Theorem and Chinese Remainder Theorem (CRT).

Answer 1

We use the fact that $6^{433} \equiv 0 \mod 3$ and $6^{433} \equiv (-1)^{433} \equiv -1\mod 7 $.

Taking $6^{433} = 3k$ ,

$$3k \equiv -1\mod 7 \implies k \equiv 2\mod 7$$

Hence $6^{433} = 3(\,7\lambda + 2\,) = 21 \lambda + 6$.

So $$6 ^{433} \equiv 6 \mod 21$$

Answer 2

Question 1. Use the Chinese remainder theorem:

you have to compute $12^{32475}\bmod 3\equiv 0^{32475}\bmod 3\equiv 0$ and, using lil' Fermat, $$12^{32475}\bmod 7\equiv 12^{32475\bmod 6}\equiv 12^3\equiv 4\cdot 12\equiv48\equiv -1\mod 7$$ Now a Bézout's relation between $7$ and $3$ is $\;7-2\cdot 3$, so the solution is $$0\cdot 7-(-1)\cdot 2\cdot 3=6\mod 21.$$

Added. On the use of the Chinese remainder theorem: When the moduli $a$ and $b$ are coprime, let $ua+vb=1$ be a Bézout's relation between $a$ and $b$. Then, a system of congruences $$\begin{cases} x\equiv \color{blue}\alpha\mod \color{blue}a,\\x\equiv \color{red}\beta\mod \color{red}b, \end{cases}$$ has a unique solution modulo $\operatorname{lcm}(a,b)=ab$: $$x\equiv \color{red}\beta\,\color{blue}{ua}+\color{blue}\alpha\, \color{red}{vb}\mod ab. $$

Question 2: it is simply that in $n-1$, $n$ is $0$ (mod $n$).

Answer 3

It is easier to apply $ $ mod Distributive Law $\,\rm= mDL\,$ vs. $\,\rm CRT\,$ in cases like this, i.e.

$\begin{align}\text{by applying}\ \ \color{#c00}ab\bmod \color{#c00}ac\ \,&\smash[b]{\underset{\textstyle\uparrow}=}\,\ \color{#c00}a(b\bmod c)\, = \text{mDL,}\ \text{ to factor out}\,\ \color{#c00}{a = 3}\\ \ \ \ \ \,(\color{#c00}3\cdot 4)^{\large\color{#0a0}{3+6k}}\bmod \color{#c00}{3}\cdot 7\ \, &\smash[t]{\overset{\textstyle\downarrow}=}\ \, \color{#c00}3(4\cdot\!\! \underbrace{12^{\large 2+6k}\!\bmod 7}_{\large (-2)^{\Large 2} (-2)^{\Large 6k}\,\equiv\ \ \color{#b8f}{4(1)}\!\!\!\!\!\!\!}\!) = 3(4\cdot \color{#b8f}4\bmod 7) = {3(2)}\end{align}$

---

Note $\,N = 32475 = 3j\ $ by $\bmod 3\!:\ N\equiv 3\!+\!(2\!+\!4)\!+\!(7\!+\!5)\equiv 0\,$ by casting out threes.

Thus $\,N = \color{#0a0}{3\!+\!6k},\,$ by $\,N\bmod 6 = 3j\bmod 6 = 3\underbrace{(j\bmod 2)}_{1\ {\rm by\ } N\rm\ odd\ }= 3(1),\, $ again by $\,\rm mDL$.

---

For $(2)$ by definition $\bmod n\!:\,\ n\!-\!1\equiv -1\iff n\mid (n\!-\!1)-(-1) = n;\ $ it's true $\,n\mid n$

More conceptually: $\ \bmod n\!:\ \color{#c00}{n\equiv 0}\,\Rightarrow\, \color{#c00}n-1\equiv \color{#c00}0-1\equiv -1\, $ by the Congruence Sum Rule

Therefore we conclude that $ \,(n-1)(n-1)\equiv (-1)(-1)\equiv 1\ $ by the Congruence Product Rule

Or $\ \, \color{#c00}{n- 1\equiv -1}\,\Rightarrow\, (\color{#c00}{n-1})^2\equiv (\color{#c00}{-1})^2\equiv 1\ $ by the Congruence Power Rule

Answer 4

I see by your comments that you haven't learned the Chinese Remainder Th and you probably haven't learned Euler's Theorem either. (Crash course and end of post)

Without them it's harder but

$12^{32475}\pmod {21} \equiv N$ means there is an integer $k$ so that

$12^{32475} = N + k21$. So

$\frac {12^{32475}}3 = \frac N3 + k\frac {21}3$

$4*12^{32474} = \frac N3 + 7k$ and $3|N$ so let $N = 3N'$

$4*12^{32474} = N' + 7k$ Now as $12 \equiv 5 \pmod 7$ we can conclude

$N' \equiv 4*5^{32474} \pmod 7$.

Now $5^2 = 25 \equiv 4 \pmod 7$ so

$N' \equiv 4*4^{16237} \equiv 4^{16238} \pmod 7$.

And $4^2 \equiv 16 \equiv 2 \pmod 7$ so

$4^{16238}\equiv 2^{8119} \pmod 7$

And $2^3 \equiv 8 \equiv 1 \pmod 7$ so

$N' \equiv 8^{2703}*2 \equiv 1^{2703}*2 \equiv 2 \pmod 7$.

So $N = 3N' =6$ so $N \equiv 6\pmod{21}$.

=====

Chinese remainder Theorem.

If you have $x = a \pmod m$ and $x \equiv b \pmod n$ and $\gcd(m,n)=1$. Then there is unique solution what $x\pmod{mn}$.

For example if $x \equiv 2 \pmod 6$ and $x \equiv 5 \pmod 7$ then there is only one possible value for $x\pmod{42}$ where $x = 2 + 6k = 4 + 7j$ and that is $x \equiv 32 \pmod{42}$.

So if $12^{32475} \equiv 0 \pmod 3$. And $12^{32475} \equiv N \pmod 7$ whe can figure out if $x \equiv 0 \pmod 3$ and $x \equiv N \pmod 7$ then we will be able to solve $x \pmod{21}$.

Now Fermat's Little Theorem. If $p$ is a prime and $\gcd(a,p) = 1$ then $a^{p-1} \equiv 1 \pmod p$.

So $12^6\equiv 1 \pmod 7$.

So $12^{32475} = 12^{6*5412 + 3}\equiv (12^6)^{5412}*12^3\pmod 7$

$\equiv 12^3 \equiv 5^3 \equiv 25*5\pmod 7$

$\equiv 4*5 \equiv 20\equiv 6\pmod 7$.

So we have $12^{32475}\equiv 0 \pmod 3$ and $12^{32475}\equiv 6\pmod 7$.

So $x \equiv 0 \pmod 3$ and $x \equiv 6 \pmod 7$ so $x = 0+3k = 6 + 7j$ and the only solution (between $0$ and $41$) is $12^{32475}\equiv 6\pmod {21}$

======

I don't understand this: n-1= -1 mod n. Where is this from? And does this line become the next line?

Bear in mind that if $a \equiv b \pmod n$ then for any multiple of $k$ we know $a + nk\equiv a \equiv b \pmod n$.

$-1 \equiv -1 \pmod n$

So $-1 + n \equiv -1 \pmod n$

And $n-1 \equiv -1 \pmod n$.

It is certainly the case that $n|(n-1) -(-1) = n$ and that is the definition of $n-1\equiv -1\pmod n$.

The alternative definition is that there exist an integer $k$ so that $n-1 = -1 + kn$ and that is certainly true.

So $n-1 \equiv -1 \pmod n$ so $(n-1)*(n-1)\equiv (-1)*(-1) \pmod n \equiv 1\pmod n$.