+0

Remainder Question

+1
172
6
+11

So I was doing some math, and I came across this question.

What is the remainder when $$2019^{2019}$$ is divided by $$2020$$?

So, I thought, well, I definitely can't do that in my head!  I did find a way to get the answer, but I was wondering if there was a simpler way to obtain the answer?

This is how I did it. By the way, I put the expression equal to its remainder.

$$1^1/2=1$$

$$2^2/3=2$$

$$3^3/4=3$$

$$4^4/5=1$$

$$5^5/6=5$$

Then I saw a pattern (kind of). The answer is in fact $$2019$$, so I was correct in my reasoning, but I was wondering if anyone had a different approach to the question.

Oh, and you are not allowed to use a calculator.

Edit: Realized that 256 divided by 5 has a remainder of 1...

Jan 23, 2020

#1
+21951
+2

How did you get the remainder of 44 when divided by 5 to be 4?

44 = 256

Divide 256 by 5 and you get a quotient of 51 and a remainder of 1.

Jan 23, 2020
#2
+11
+2

Oh! Thanks for catching that error!

#3
+11
+1

Well, my pattern seems to work, but it kind of broke at 5. Will it break at all multiples of 5? Or is there something else?

Based on what I am seeing, it seems as though all times a multiple of 5 appears, then it has a remainder of 1.

Jan 23, 2020
#4
+1

Hello,

https://www.quora.com/What-is-the-remainder-when-2019-2019-is-divided-by-2020 from Quora.

Jan 23, 2020
#5
+1

By the way, your pattern works! If you looked at the link, there is a solution similar to yours.

Although If it asked for proof (In competitions etc..) using mods is a must and not just patterns.

Jan 23, 2020
#6
+110235
+2

Consider the sequence you discovered.

You found that

$$1^1\;\mod2 = 1\;or \;-1\\ 2^2\;\mod3=+1\\ 3^3\;\mod4=-1\\ 4^4\;\mod5=+1$$

NOTE: If a number (mod n) = -1 Then the number divided by n will have a raimainder of  n-1

If you want me to discuss this more I can.

So it looks like

$$n^n\mod(n+1)=+1 \text{ when n is even}\\ n^n\mod(n+1)=-1 \text{ when n is odd}\\$$

So can I prove that his is always the case??

$$n\mod(n+1)=-1\\ so\\ n^n\mod(n+1)\equiv (-1)^{n+1}$$

-1 raised to an even power will be +1

-1 raised to an odd power will be -1

so

$$\frac{n^n}{n+1}\quad\text{has a remainder of +1 when n is an even positive integer}\\ and\\ \frac{n^n}{n+1}\quad\text{has a remainder of n when n is an odd positive integer}\\ \text{which means}\\ \frac{2019^{2019}}{2020}\quad\text{has a remainder of 2019 }\\$$

Jan 23, 2020