5

I was messing around with my calculator earlier today. I graphed the function $6^x \pmod{11}$, and I noticed a pattern, and I "discovered" the following:

$$6^x ≡ 2^{10-x} \pmod{11}$$

This works whenever $x$ is an integer between $0$ and $10$, inclusive. Likewise, these also seem to work:

$$4^x ≡ 3^{10-x} \pmod{11}$$ $$5^x ≡ 9^{10-x} \pmod{11}$$ $$7^x ≡ 8^{10-x} \pmod{11}$$ $$10^x ≡ 1^{10-x} \pmod{11}$$

I have two main questions:

  • What causes the pairs $(1,10)$, $(2,6)$, $(3,4)$, $(5,9)$, and $(7,8)$?
  • Why do relationships like this exist in the first place?
PhiNotPi
  • 2,661
  • 3
  • 23
  • 36
  • 3
    Because $6\cdot 2 = 12 \equiv 1 \pmod{11}$, and $11$ is prime, so $a^{11-1} \equiv 1 \pmod{11}$ for all $a$ not divisible by $11$. Your pair $(1,,10)$ doesn't actually work, $10^3 \equiv 10 \pmod{11}$. – Daniel Fischer Jul 04 '13 at 18:24
  • With the pair $(1,10)$, I must have accidentally tested only even exponents. – PhiNotPi Jul 04 '13 at 18:40

1 Answers1

3

First note that, for any integer $x$, $$6^x\equiv 2^{10-x}\bmod 11 \;\iff\; 12^x=6^x\cdot 2^x\equiv 2^{10}\bmod 11.$$ Then note that $12\equiv 1\bmod 11$, so that $12^x\equiv 1\bmod 11$ for any $x$, and also that $2^{10}\equiv 1\bmod 11$, which one can compute directly: $$2^{10}=1024=(11\cdot 93)+1\equiv 1\bmod 11$$ or just appeal to Fermat's little theorem.

We can generalize your observation as follows: for any positive integer $n$, and for any integers $a$ and $b$ such that $ab\equiv 1\bmod n$, we have $$a^x\equiv b^{\varphi(n)-x}\bmod n$$ for all $0\leq x\leq \varphi(n)$ (and indeed, for all integers $x$, because we can make sense of the multiplicative inverse of $a$ and $b$ modulo $n$).

Zev Chonoles
  • 129,973