2
  1. $2^{47} \bmod 23$
  2. $776^{79} \bmod 7$
  3. $12347369^{3458} \bmod 19$
  4. $5^{18} \bmod 13$
  5. $23^{560} \bmod 561$

I really don't understand how to calculate the ones to powers. Could anyone explain how to do one of these examples?

user26486
  • 11,331
Allie Maz
  • 23

2 Answers2

1

First make sure that you reduce the element which you want to exponentiate. After this you should apply Euler's theorem to reduce the exponent (note that this is only possible if the element you want to exponentiate is relatively prime to the modulus.

I will do $776^{79}$ as an example:

$776^{79}\equiv 6^{79}\bmod 7$ since $776\equiv 6 \bmod 7$

$6$ and $7$ are relatively prime so we can use euler's theorem, it tells us $6^{\varphi(7)}\equiv 1 \bmod 7$. Since $7$ is prime $\varphi(7)=7-1=6$ so we have $6^{6}\equiv 1 \bmod 7$. We can now finish:

$6^{79}=6^{78}\cdot 6=(6^6)^{13}\cdot 6\equiv 1\cdot 6\equiv 6\bmod 7$

Therefore $776^{79}\equiv 6 \bmod 7$.

user26486
  • 11,331
Asinomás
  • 105,651
  • 1
    And there are sometimes useful tricks. For example,$776\equiv -1\pmod{7}$, so $776^{79}\equiv-1\pmod{7}$, meaning that the least positive residue is $6$. Note that a similar trick works for $5^{18}$ modulo $13$. For $5^2\equiv -1$, so $5^{18}\equiv -1$, the remainder is $12$. – André Nicolas May 03 '15 at 01:11
  • Yes, I didn't say that because I tried to make the solution as general as I could, good eye though. – Asinomás May 03 '15 at 01:13
  • Thank you so much! I didn't know to use the Euler's theorem and that was where I was getting stuck.

    Also thank you for that trick as well, I'll try to use that more often as well.

     – Allie Maz May 03 '15 at 01:13
  • @Gamamal: You are right to do it that way, OP can use the same idea elsewhere. The only one that is a bit different is $561$. – André Nicolas May 03 '15 at 01:15
  • How is 561 different? Because it isn't relatively prime? – Allie Maz May 03 '15 at 01:16
  • yes, you are going to have to calculate the residues modulo each prime and then stitch them back up mod 561 using the chinese remainder theorem. – Asinomás May 03 '15 at 01:17
  • Ok, I think I got it. Thanks again for your help! – Allie Maz May 03 '15 at 01:28
  • @AllieMaz you could add an answer to this question also showing your solution of the others... just a suggestion:-) – Joffan May 03 '15 at 03:27
  • @AllieMaz Because it isn't prime, not 'relatively prime'. $a_1,a_2,\ldots,a_n$ are relatively prime (i.e. coprime) if $\gcd(a_1,a_2,\ldots,a_n)=1$ (usually shortened to $(a_1,a_2,\ldots,a_n)=1$). Being relatively prime is not defined for a single integer. – user26486 May 03 '15 at 21:13
0

Euler's theorem ($(a,n)=1\,\Rightarrow\,a^{\phi(n)}\equiv 1\pmod{\!n}$) implies Fermat's little theorem (FLT): $p\nmid a\,\Rightarrow\, a^{p-1}\equiv 1\pmod{\! p}$, since $\phi(p)=p-1$ ($p$ is prime).

$\bmod 23\!:\ 2^{47}\stackrel{\text{FLT}}\equiv 2^{47\!\pmod{\! 22}}\!\equiv 2^3\equiv 8$.

$\bmod 7\!:\ 776^{79}\equiv (-1)^{79}\equiv -1\equiv 6$.

$\bmod 19\!:\ 12347369^{3458}\equiv 10^{3458}\stackrel{\text{FLT}}\equiv 10^{3458\!\pmod{\! 18}}\!\equiv 10^2\equiv 5$.

$\bmod 13\!:\ 5^{18}\equiv 25^9\equiv (-1)^9\equiv -1.$

$561=3\cdot 11\cdot 17$.

$\bmod 3\!:\ 23^{560}\equiv (-1)^{560}\equiv 1$.$\:$ $\bmod 11\!:\ 23^{560}\equiv 1^{560}\equiv 1$.

$\bmod 17\!:\ 23^{560}\stackrel{\text{FLT}}\equiv 23^{560\!\pmod{\! 16}}\!\equiv 23^0\equiv 1$.

$3,11,17\mid 23^{560}-1\,\Rightarrow\, 561\mid 23^{560}-1$, since $\text{lcm}(3,11,17)=561$.

We got lucky that $23^{560}\!\bmod{7}=23^{560}\!\bmod{11}=23^{560}\!\bmod{17}$. This is often not the case
($\!\bmod{}\!$ here (unlike above) is an operation that gives the least residue, as opposed to an equivalence relation, in which integers with the same residues are equivalent, denoted $\equiv$).

In general, finding residues mod composite $n$ can be done using the following algorithm. CRT (Chinese remainder theorem) says that given residues mod coprime $a_i$, there is a unique residue mod $a_1a_2\cdots a_k$ (and trivially a residue mod $a_1a_2\cdots a_k$ gives unique residues to coprime $a_i$).

E.g., find $18^{55}\!\bmod{170}$. $\: 170=2\cdot 5\cdot 17$.

$\bmod 2\!:\ 18^{55}\equiv 0\,\Rightarrow\, 18^{55}=2k$.

$\bmod 5\!:\ 18^{55}\equiv 3^{55}\stackrel{\text{FLT}}\equiv 3^{55\!\pmod{\! 4}}\!\equiv 3^3\equiv 2\equiv 2k\,\Leftrightarrow k\equiv 1\,\Rightarrow\, k=5l+1$.

$\bmod 17\!:\ 18^{55}\equiv 1^{55}\equiv 1\equiv 2(5l+1)\equiv 10l+2\,\Leftrightarrow\, 10l\equiv -1\equiv 50\,\stackrel{:10}\Leftrightarrow\, l\equiv 5$.

$18^{55}=2(5(17m+5)+1)=2(85m+26)=170m+52$.

user26486
  • 11,331