Hint for finding the remainder when $2018^{2019}$ is divided by 13

Question

I have been thinking of how to answer this. The question is find the remainder of:

$$\frac {(2014^{2015}) \space (2016^{2017}) + 2018^{2019} \space}{13}$$

This is what I was thinking:

Since $ 13 \space|\space 2015 $, we know that:

$2014 \space \equiv \space -1 \space (mod \space 13)$

$2016 \space \equiv \space 1 \space (mod \space 13)$

Up to this point:

$$\frac {((-1)^{2015}) \space (1^{2017}) + 2018^{2019} \space}{13}$$

But I cant get rid of the 2018 since I cant get it to be congruent with a 1 or -1. Any hints?

What is $x$? Is it a variable or the multiplication operator? — rubberchicken, Mar 04 '14 at 03:03
Try using this identity: $a^{\phi(b)} \equiv 1 \mod b$, where a and b are relatively prime. — rubberchicken, Mar 04 '14 at 03:06
@user132586 edit your post then please. it's a 2 character edit, and therefore(weirdly) above my privileges. — Guy, Mar 04 '14 at 03:07
@user132586 you can either use * or \times for multiplication (or parentheses) — MT_, Mar 04 '14 at 03:07
Also, I had to use the calculator to find that 13 divides 2015. Is there a way to do this mentally? — user132586, Mar 04 '14 at 03:10
You can use long division or something like this: You know that $13$ divides $1300$, so subtract from $2015$ to get 715. You also know $13 | 650$ so subtract 650 to get 65. You know that $13 | 65$, so $13 | 2015$ — MT_, Mar 04 '14 at 03:12
@user132586 I suppose at the end of the day, you have to notice the $13|2015$ thing by yourself. — Guy, Mar 04 '14 at 03:17

score 2 · Answer 1 · answered Mar 04 '14 at 03:11

2

For the last part, $$a^{\phi (b)} \equiv 1 \pmod b$$

with $a, b$ coprime. We want $\pmod {13}$, and $\phi(13) = 12$ since $13$ is prime.

Thus, $2018^{2019} \equiv (2018^{12})^{168} * (2018)^3 \equiv (1)^{168} (3)^3 \equiv 1 \pmod {13}$

You can take it form here.

answered Mar 04 '14 at 03:11

MT_

19,603
9
40
81

How did you collapse $2018^3$ to $3^3$? – user132586 Mar 04 '14 at 03:26
1

To add on to what @user92774 said, he collapsed (2018)^3 to (2018-2015)^3 (mod 13) = (3)^3 (mod 13) – Scarecrow Mar 04 '14 at 19:25

score 2 · Accepted Answer · answered Mar 04 '14 at 03:15

HINT: You have the right idea. Euler's Theorem, as rubberchicken mentioned, states the following $$ a^{\phi(q)} \equiv 1 \bmod q $$ for $a$ relatively prime to $q$. Note that $\phi(q)$ is the totient function, or the number of integers less than or equal to $q$ that are relatively prime to $q$ (for $13$ this is $12$). Thus, we get: $$ 2018^{12} \equiv 1 \bmod 13 $$

See if you can get it from there.

Hint for finding the remainder when $2018^{2019}$ is divided by 13

2 Answers2