Get all values for exponent in congruential equation

Question

I am stuck on an exercise on modular arithmetic. I found a similar question here, but I don't think it answers my question completely.

My problem is:

Solve $$ 2^x \equiv 11 \pmod {21} $$

over $\Bbb N$. I know the solution should be $$x = 5 + 6k$$ where $k \in \Bbb N_0$ ($\Bbb N$ with 0 included).

My problem is, that I don't know how they got this solution.

My solution was:

$$ 2^x \equiv 11 \pmod {21} $$ $$(\text{multiply by } 2 \equiv 11^{-1}\pmod{21}) $$ $$2^{x+1}\equiv1\pmod{21}$$

According to Euler's Theorem, $a^{\phi(n)}\equiv1\pmod{n} \iff gcd(a,n) = 1$. Where $\phi(n)$ is Euler's Phi Function.

It means that because $gcd(21, 2) = 1$, $$ x+1 = \phi(21)$$

$$\implies x=\phi(21)-1 = 12-1=11$$

Also, $x$ is periodic modulo 21 and its period is $\phi(21) = 12$. My solution therefore is

$$x = 11 + 12k, k\in \Bbb N_0$$

What am I doing wrong? I can get to $x=5$ only by trial & error and I don't know how to get $6k$ as the period at all.

I would like to know how to solve this type of problems in general. If $11^{-1}$ wasn't 2 I wouldn't know what to do at all, because I couldn't join the exponents.

Answer 1

The problem is that Euler's theorem does not give the smallest exponent for which $a^k\equiv1\bmod n$. That smallest exponent is given by the Carmichael function $\lambda(n)$, and $\lambda(21)=6$ (as compared to $\varphi(21)=12$), so we have $$2^6\equiv1\bmod21$$ This yields $x=11+6k=5+6k$, as desired.

Answer 2

By the Chinese remainder theorem the equation is equivalent with the pair of equations $$2^x \equiv 11 \equiv 2 \pmod {3} \text{ and }2^x \equiv 11 \equiv 4 \pmod {7}$$ with, observing that $2^3 \equiv 1 \pmod 7$, solutions $$x \equiv 1 \pmod 2 \text{ and } x \equiv 2 \pmod 3$$

These combine into $x \equiv 5 \pmod 6$