Why 2^923 mod 15 = 8 (in-depth)

For any fixed natural number m greater than 1, we say that the integer a is congruent to the integer b modulo m if a − b is divisible by m. Please find the remainder when 2^923 is divided by 15.

To compute $2^{923}\bmod15$, note that $\gcd(2,15)=1$ and Euler’s totient $\varphi(15)=8$, so

$$ 2^8\equiv1\pmod{15}. $$

Thus

$$ 2^{923}\equiv2^{923\bmod8}\equiv2^3\equiv8\pmod{15}. $$

Answer: The remainder is $8$.

Thank you for finding the remainder, but I don’t understand what you said, please explain this “Euler’s totient φ” business.

Sure! Let me break it down step by step.

---

1. What is Euler’s totient function, $\varphi(n)$?

• $\varphi(n)$ is the number of positive integers up to $n$ that are coprime to $n$ (i.e.\ they share no prime factors with $n$).

• For example, to compute $\varphi(15)$:

  1. Factor $15 = 3 \times 5$.

  2. Use the formula for a product of two distinct primes:

     $$ \varphi(p\cdot q) \;=\; (p-1)\,(q-1). $$

  3. Thus

     $$ \varphi(15) \;=\;(3-1)\,(5-1)\;=\;2\times4\;=\;8. $$

  So there are 8 numbers in $\{1,2,\dots,15\}$ that are coprime to 15: $1,2,4,7,8,11,13,14$.

---

2. Euler’s theorem (a generalization of Fermat’s little theorem)

Statement. If $\gcd(a,n)=1$, then

$$ a^{\varphi(n)} \;\equiv\;1 \pmod{n}. $$

• “$\gcd(a,n)=1$” means $a$ and $n$ have no common prime factors.
• So raising $a$ to the $\varphi(n)$-th power always gives a remainder of 1 when divided by $n$.

---

3. Applying it to $2^{923}\bmod15$

1. Check that $\gcd(2,15)=1$. ✔

2. Compute $\varphi(15)=8$.

3. By Euler’s theorem,

   $$ 2^8 \equiv 1 \pmod{15}. $$

4. Therefore powers of 2 modulo 15 repeat every 8 steps. In particular,

   $$ 2^{923} \;=\; 2^{8\cdot115 + 3} \;=\; \bigl(2^8\bigr)^{115}\;\times\;2^3 \;\equiv\; 1^{115}\;\times\;2^3 \;=\; 2^3 \;=\; 8 \;\pmod{15}. $$

5. Remainder = 8.

---

4. Why this helps

Without Euler’s theorem, you’d have to multiply 2 by itself 923 times and reduce mod 15 each time—impractical by hand. The totient function tells you exactly when the pattern of remainders resets.

I hope this clarifies what $\varphi(n)$ is and how Euler’s theorem lets us simplify huge exponents!

What’s the reasoning for going from $2^8\equiv1\pmod{15}$ to $2^{923}\equiv2^{923\bmod8}\pmod{15}$?

The key property you’re using is that if you know

$$ a^M \equiv 1 \pmod{n}, $$

then for any exponent $E$ you can write $E$ in the division‐with‐remainder form

$$ E = M\cdot Q + R,\quad 0 \le R < M, $$

and get

$$ a^E = a^{M\cdot Q + R} = \bigl(a^M\bigr)^Q \cdot a^R \equiv 1^Q \cdot a^R \;=\;a^R \pmod{n}. $$

---

Applying it to our case

1. We know $2^8 \equiv 1 \pmod{15}$.

2. Divide the exponent 923 by 8:

   $$ 923 = 8 \times 115 + 3, $$

   so here $M = 8$, $Q = 115$, $R = 3$.

3. Then

   $$ 2^{923} = 2^{8\cdot115 + 3} = \bigl(2^8\bigr)^{115}\times 2^3 \equiv 1^{115}\times 2^3 = 2^3 \pmod{15}. $$

4. Hence you only need to compute $2^3\equiv8$, and you never have to multiply out all 923 factors.

---

So whenever you have a “cycle” $a^M\equiv1\pmod{n}$, you can reduce the exponent modulo $M$. That’s exactly why

$$ 2^{923}\equiv 2^{923\bmod8}\pmod{15}. $$

How do we know $\varphi(p\cdot q) \;=\; (p-1)\,(q-1)$?

There are two classic ways to see why, for two distinct primes $p$ and $q$,

$$ \varphi(pq)\;=\;(p-1)(q-1). $$

---

1. Multiplicativity of $\varphi$

Euler’s totient function is multiplicative on coprime arguments:

$$ \text{if }\gcd(m,n)=1,\quad\text{then }\varphi(mn)=\varphi(m)\,\varphi(n). $$

Since $p$ and $q$ are primes, $\gcd(p,q)=1$, and we know

$$ \varphi(p)=p-1,\quad \varphi(q)=q-1 $$

(because out of the $p$ numbers $1,2,\dots,p$, exactly the multiples of $p$ — just “$p$” itself — fail to be coprime, leaving $p-1$ survivors; similarly for $q$). Hence

$$ \varphi(pq) =\varphi(p)\,\varphi(q) =(p-1)(q-1). $$

---

2. Direct “inclusion–exclusion” count

Count how many integers $1\le k\le pq$ are not coprime to $pq$. Exactly those that share a factor with $pq$, i.e.\ those divisible by $p$ or by $q$:

• Multiples of $p$ in that range: $\displaystyle \frac{pq}{p}=q$ of them ($p,2p,\dots,qp$).
• Multiples of $q$ in that range: $\displaystyle \frac{pq}{q}=p$ of them ($q,2q,\dots,pq$).
• But we’ve counted multiples of both $p$ and $q$ (i.e.\ multiples of $pq$) twice; there is exactly 1 of those ($pq$ itself).

By inclusion–exclusion, the total count of “bad” numbers is

$$ \#\{\text{divisible by }p\} + \#\{\text{divisible by }q\} - \#\{\text{divisible by both}\} = q + p - 1. $$

Since there are $pq$ numbers in all, the count of good (coprime) ones is

$$ pq - (q + p -1) = pq - p - q + 1 = (p-1)(q-1). $$

Either viewpoint immediately yields

$$ \boxed{\varphi(pq)=(p-1)(q-1).} $$

How is Euler’s theorem proved?

Here is a classic, elementary proof of Euler’s theorem:

---

Setup: the reduced residue system mod $n$

Let

$$ n>1,\quad a\in\mathbb{Z},\quad\gcd(a,n)=1. $$

Define the reduced residue system modulo $n$ as the set

$$ R \;=\;\{\,r_1,r_2,\dots,r_{\varphi(n)}\} $$

of all positive integers $<n$ that are coprime to $n$. By definition, $|R|=\varphi(n)$.

---

Proof by “permutation of residues”

1. Multiply each element of $R$ by $a$, and reduce modulo $n$. Because $\gcd(a,n)=1$, none of the products

   $$ a\,r_1,\;a\,r_2,\;\dots,\;a\,r_{\varphi(n)} $$

   can share a nontrivial factor with $n$. Hence each $a\,r_i\pmod n$ is again in the reduced residue system.

2. No collisions. If for two indices $i\neq j$ we had

   $$ a\,r_i \equiv a\,r_j \pmod n, $$

   then

   $$ a\,(r_i - r_j)\equiv0\pmod n \quad\Longrightarrow\quad n\bigm|\bigl(r_i-r_j\bigr), $$

   which forces $r_i\equiv r_j\pmod n$. But $0<r_i,r_j<n$, so $r_i=r_j$, contradicting $i\neq j$. Thus multiplication by $a$ permutes $R$.

3. Compare the two products. Consider the product of all members of $R$:

   $$ P \;=\; r_1\,r_2\cdots r_{\varphi(n)}. $$

   On one hand, that’s $P$. On the other hand, because the list $\{a\,r_i\pmod n\}$ is just a re‑ordering of the same $r_i$’s, its product is also

   $$ a^{\varphi(n)}\,P \;\equiv\; P\pmod n. $$

   Hence

   $$ a^{\varphi(n)}\,P \;\equiv\;P\pmod n \quad\Longrightarrow\quad a^{\varphi(n)}\equiv1\pmod n \quad\Bigl(\gcd(P,n)=1\Bigr). $$

That completes the proof.

---

Alternate (group‑theoretic) viewpoint

The integers coprime to $n$, under multiplication mod $n$, form a finite group of order $\varphi(n)$. In any finite group, Lagrange’s theorem says that the order of any element divides the group order, and in particular $x^{|G|}=e$. Taking $x=[a]$ in the group $(\mathbb{Z}/n\mathbb{Z})^\times$ shows

$$ [a]^{\varphi(n)} = [1] \quad\Longleftrightarrow\quad a^{\varphi(n)}\equiv1\pmod n. $$