3
$\begingroup$

I'm teaching myself about congruences. One of the problems in the old number theory book I'm using is $$x^{10} \equiv 1 \pmod{11}$$ Using my calculator (and confirmed with Wolfram Alpha), I tested integers 1 through 11; only 11 yields a residue other than 1. The fact that only multiples of 11 do not satisfy the congruence really surprised me.

My book doesn't offer an explanation, and I'm not able to reason through it. I don't know if it's a complicated problem that the book is just using as a fun example of congruences or if the reasoning is at my novice level and I'm just not seeing it. I tried thinking of it as $(x^2)^5 \equiv 1 \pmod {11}$ and taking the 5th root, but that promptly yielded wrong answers.

Then I was wondering if there's some relationship between base 10, 10 in the exponent, and 11 (one greater than 10) as the mod.

Any hints or guidance?

$\endgroup$
1
  • 1
    $\begingroup$ look up Fermat's Little Theorem. $\endgroup$
    – Set
    Jan 6, 2016 at 2:27

5 Answers 5

3
$\begingroup$

This is a consequence of the much more general Fermat's little theorem, which implies that whenever the base $p$ is prime, $a^{p - 1} \equiv 1 \pmod{p}$ for $a$ not divisible by $p$ (becuase then $a \equiv 0 \pmod{p}$).

This can be seen in many different ways, and there are some proofs in the Wikipedia article or almost any elementary number theory textbook. This is deeply related to the fact that the integers $\mod p$ form a group, and can be proven as a consequence of Lagrange's theorem.

$\endgroup$
2
$\begingroup$

This is known as the little fermat theorem https://en.wikipedia.org/wiki/Fermat's_little_theorem

$\endgroup$
1
  • $\begingroup$ Awesome -- thank you! I'll check out the link. $\endgroup$
    – DBS
    Jan 6, 2016 at 2:29
2
$\begingroup$

As the other answers say, this is an instance of Fermat's Little Theorem. The theorem can also be expressed as $$x^p \equiv x \pmod p$$ for all $x$. (So in your case if you multiply both sides by $x$, then you get $x^{11} \equiv x \pmod {11}$, and now it also holds for $x \equiv 11$ too.)

A nice proof of this is to consider, for a prime $p$, the product $(p-1)! = 1\cdot2\cdots(p-1).$ Now multiply every term by $x$; since there are $p-1$ terms in the product, we have $$x^{p-1}(p-1)! = (1x)\cdot(2x)\cdots((p-1)x)$$ But using results from modular arithmetic we know that the right-hand side, taken modulo $p$, is actually just a reordering of $(p-1)!$. We therefore have $$x^{p-1}(p-1)! \equiv (p-1)! \pmod p$$ and multiplying by the inverse of $(p-1)!$ gives the result.

If it helps, here is a concrete example of the proof: let's keep $p=11$ and choose $x=2$. Then $$2^{10}10! = 2\cdot4\cdot6\cdot8\cdot10\cdot12\cdot14\cdot16\cdot18\cdot20$$ so reducing modulo 11, $$2^{10}10! \equiv 2\cdot4\cdot6\cdot8\cdot10\cdot1\cdot3\cdot5\cdot7\cdot9 \pmod{11}$$ and the key observation is that the right-hand side is again $10!$.

$\endgroup$
1
  • $\begingroup$ Very cool. Your concrete example is very helpful! $\endgroup$
    – DBS
    Jan 6, 2016 at 2:51
1
$\begingroup$

Fermat's little theorem: If p is a prime that does not divide a then $a^{p-1}= 1 (mod p)$. (Not fast enough!)

$\endgroup$
1
$\begingroup$

My favorite proof of this uses induction to show that $n^p \equiv n \pmod{p}$ for all $n\geq 0$.

This is obvious for $n=0$. For the inductive step, we expand $(n+1)^p$ using the binomial theorem. It is a straightforward exercise that $\binom{p}{k}$ is divisible by $p$ for all $0<k<p$, so we have $(n+1)^p \equiv n^p + 1^p \equiv n + 1 \pmod{p}$.

To conclude that $n^{p-1} \equiv 1 \pmod{p}$, we simply multiply by the multiplicative inverse of $n$ modulo $p$, which exists precisely when $(n,p)=1$.

$\endgroup$
1
  • 1
    $\begingroup$ Another way to end your proof is: If $p\mid n\left(n^{p-1}-1\right)$ and $(n,p)=1$, then by Euclid's Lemma $p\mid n^{p-1}-1$. $\endgroup$
    – user236182
    Jan 7, 2016 at 0:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .