Htykuut

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

For the first, we have $7^{4275}=(7{^{427}})^{10}cdot7^5$, because $4275=427cdot10+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$.

You can have a much faster solution:

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

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

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

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 bpmod q$ then $a^k equiv b^k pmod q$ and therefore if $a^k equiv 1 pmod q$ then $a^{mk +r} = (a^k)^mcdot a^r equiv (1)^mcdot a^requiv a^rpmod d$.

So we know by FLT then $7^{10}equiv 1pmod 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^5equiv 7^5pmod {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.)