1
$\begingroup$

How would you evaluate $ 2^{2143} \pmod{17}?$

For instance, I was looking through my notes and the example I have is : $5^{131} \pmod{14}$

We look at the powers $ 5^i$ modulo $14$ and notice that they repeat at $i = 6$

Now since $131 = 5 \pmod{6}$ then $5^{131} = 5^5 = 3 \pmod{14}$

The answer is $3$. However, I do not understand this logic at all.

$\endgroup$
6
  • 3
    $\begingroup$ Helps to note that, by Little Fermat, $2^{16}\equiv 1 \pmod {17}$ $\endgroup$
    – lulu
    Jun 17, 2017 at 13:54
  • 3
    $\begingroup$ And by Euler's theorem, $5^6 \equiv 1\pmod{14}$. $\endgroup$
    – peterwhy
    Jun 17, 2017 at 13:54
  • $\begingroup$ @lulu how do you know by Little Fermat to do that? Also how would I apply that to the question? $\endgroup$
    – Maggie
    Jun 17, 2017 at 13:58
  • $\begingroup$ @peterwhy how would I apply this? $\endgroup$
    – Maggie
    Jun 17, 2017 at 13:58
  • $\begingroup$ Since $2143 = 16n + 15$, $$2^{2143} \equiv 2^{16n + 15} \equiv (2^{16})^n \cdot 2^{15} \equiv 1\cdot 2^{15} \pmod{17}$$ $\endgroup$
    – peterwhy
    Jun 17, 2017 at 14:00

3 Answers 3

4
$\begingroup$

Notice that $$2^4=16\equiv16-17\equiv -1\pmod{17}$$ Also notice that $$2^8=2^4\cdot 2^4\equiv (-1)\cdot (-1)\equiv 1\pmod{17}$$ Then $$2^{2143}=(2^8)^{267}\cdot 2^7\equiv 1^{267}\cdot 2^7\equiv 2^7=128\equiv9\pmod{17}$$

$\endgroup$
3
$\begingroup$

Fermat's Little Theorem:

If $p$ is a prime and $gcd(a,p) = 1$, then $a^{p-1} \equiv 1 (mod \; p)$.

Generalization of Fermat's Little Theorem (Euler's Theorem):

Let $a,n \in \mathbb{N}$ and $gcd(a,n) = 1$, then $a^{\phi(n)} \equiv 1 (mod \; n)$, where $\phi(n)$ = number of positive integers less than $n$ and coprime to $n$.

In the first example, 17 is a prime and $gcd(2, 17) = 1$. Hence $2^{16} \equiv 1 (mod \; 17)$. Hence $2^{2143} = 2^{16 \times 133 + 15} = (2^{16})^{133} \cdot 2^{15} \equiv 1^{133} \cdot 2^{15} \equiv 2^{15} (mod \; 17)$. Also note that $2^4 \equiv -1 (mod \; 17) \implies 2^{15} = (2^4)^3 \cdot 2^3 \equiv (-1)^3 \cdot 8 \equiv -8 \equiv 9 (mod \; 17)$.

In the second example, we have to use the generalization because 14 is not a prime and $gcd(5,14) = 1$. Also, $\phi(14) = \phi(2 \times 7) = \phi(2) \times \phi(7) = 1 \times 6 = 6$. (This comes from the fact that $\phi$ is a multiplicative function. A number theoretic function $f$ is multiplicative if $f(mn) = f(m) \cdot f(n)$ whenever $gcd(m,n) = 1$).

Hence $5^6 \equiv 1 (mod \; 14)$. Also, $131 = 6 \times 21 + 5$. Thus, $5^{131} = (5^6)^{21} \cdot 5^5 \equiv 1^{21} \cdot 5^5 \equiv 5^5 (mod \; 14)$.

If you want more transparency in the logic, write $131 = 6q + r$ where $q$ is the quotient and $r$ is the remainder when 131 is divided by 6. Repeat the calculation above using $q$ and $r$ to note that the value of $q$ has no effect on the answer. All that matters is the value of $r$ which is nothing but $131 (mod \; 6)$.

$\endgroup$
1
$\begingroup$

Without getting into equivalence classes, multiplication mod $n$ is associative. That means that if you know $i$ such that $a^i \mod n=1$ then $a^k \mod n = (a^i \mod n)^{\mathrm{quot}(k,i)} a^{k \mod i} \mod n=a^{k \mod i} \mod n$, where quot represents the quotient in integer division. For a prime modulus, multiplication mod $n$ also has an inverse, so that such a (nonzero) $i$ will always exist and in fact will be in $\{ 1,2,\dots,n-1 \}$. In fact little Fermat's theorem tells us that if $n$ is prime and the base isn't divisible by $n$ then $i=n-1$. So you could have figured out that $i=16$ in your case without brute force.

(Side note: not sure how better to format this, since I don't really want to use the $\equiv$ notation in this case.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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