0

Find the least non residue of the following $7^{4275} \mod 11$.

I have the solution for the problem and it is the following:

$7^{10} ≡ 1 \mod 11$

$7^{4275} = (7^{10})^{427} \times 7^{5} \mod 11$ ----> why this particular multiplication case?

$≡ 7^{5} \mod 11$

$≡ 16807 \mod 11$

$≡ 1527 \times 11 + 10 \mod 11$ ----> I do not see where this came from. Can this be skipped and move straight to the next line?

$≡ 10 \mod 11$

$≡ -1 \mod 11$

I am having some problem trying to understand why the above steps have been done.

I am aware that Fermat's Little Theorem is used.

I have looked at the link below for some help but I am still having some trouble understanding this.

Needing help finding the least nonnegative residue

Bernard
  • 175,478
Hidaw
  • 971
  • 1
    What step do you need help understanding? (BTW, going from the second to last step to the last, it looks like it should be -1 mod 11). Also, you should use \cdot rather than x to represent multiplication. – Acccumulation Dec 05 '18 at 22:52
  • $10\not\cong1\pmod{11}$, so the last step is wrong. $10\cong -1\pmod{11}$ though. –  Dec 05 '18 at 22:53
  • What's a "least non residue"? – fleablood Dec 05 '18 at 22:54
  • @Acccumulation I have indicated with a "?" the steps that I am having some trouble understanding – Hidaw Dec 05 '18 at 22:54

3 Answers3

1

For the first, we have $7^{4275}=(7{^{427}})^{10}\cdot7^5$, because $4275=427\cdot10+5$.

Next, one could use a calculator to divide $16807$ by $11$. One gets $1527.*$, where $*$ is the part after the decimal. So, multiply $1527$ by $11$ and subtract from $16807$. You get $10$, as the residue mod $11$.

1

You can have a much faster solution:

By Fermat's little theorem, $\;7^{4275}\mod 11\equiv 7^{4275\bmod 10}\mod 11=7^5\mod 11$.

Now you compute the powers of $7\bmod 11$ recursively:

$7^2\equiv 5\mod 11$, so $\;7^4\equiv 5^2\equiv 3\mod 11$ and finally $\;7^5=7^4\,7$$\equiv 3\,7\equiv 10\mod 11$.

Bernard
  • 175,478
1

By the division property given an integer $N$ and a number $q$ then there exists unique integers $a, r$ where $N = a*q + r$ and $r$, the remainder is $0 \le r < q$.

The least non negative residue of $N \pmod q$ is precisely that $r$.

And we know if $a \equiv b\pmod q$ then $a^k \equiv b^k \pmod q$ and therefore if $a^k \equiv 1 \pmod q$ then $a^{mk +r} = (a^k)^m\cdot a^r \equiv (1)^m\cdot a^r\equiv a^r\pmod d$.

So we know by FLT then $7^{10}\equiv 1\pmod 11$, we can reduce the ridiculously huge $7^{4275}$ to $7^{10*427 + 5} = (7^{10})^{427}\cdot 7^5$ to get $7^{4275}\equiv (7^{10})^{427}\cdot 7^5 \equiv 1^{427}\cdot7^5\equiv 7^5\pmod {11}$.

Surely $7^5$ is a much more reasonable number to deal with.

$7^5 = 16807$ and we want to find a residue $\mod 11$ so we want to solve $16808 = a*11 + r$. (Actually we don't give a flying fig about $a$-- we only care about $r$.

Well, if we divide $16807$ by $11$ we get $16807 = 1527*11 + 10$.

So $7^{4275} \equiv 7^5 = 16807=1527*11 + 10 \equiv 10 \pmod {11}$.

(Do you know the trick that two find the remainder of dividing by $11$ you subtract the even number from the odd. For $16797$ the even digits are $6 + 9 =15$ And the odd digits are $1+7+7= 15$. If you subtract you get $0$ so $16797$ is divisible by $11$. For $16807$ the even digits are $6+0 =6$ adn the odd are $1+8 + 7 =16$. You subtract and you get $16-6 =10$. So the remainder is $10$. And $16807 \equiv 10 \pmod {11}$. And we don't give a flying fig about what the quotient is.)

fleablood
  • 124,253