Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
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 4 '13 at 18:24
    
With the pair $(1,10)$, I must have accidentally tested only even exponents. –  PhiNotPi Jul 4 '13 at 18:40

1 Answer 1

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$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.