How would you solve this non-calculator question?

mchen60

New member
Joined
Jan 11, 2020
Messages
2
Sorry for any inconveniences but i was wondering whether anybody could be able to help me solve this arithmetic question that i found in a Maths Olympiad Textbook, the question is to be attempted without a calculator.

What is the remainder of (2018^2018)/20?

Thanks, this problem has been gnawing at me for the past few hours and sorry for any inconvenience.
 
Last edited:

Subhotosh Khan

Super Moderator
Staff member
Joined
Jun 18, 2007
Messages
20,133
Sorry for any inconveniences but i was wondering whether anybody could be able to help me solve this arithmetic question that i found in a Maths Olympiad Textbook, the question is to be attempted without a calculator.

What is the remainder of (2018^2018)/20?

Thanks, this problem has been gnawing at me for the past few hours and sorry for any inconvenience.
Please follow the rules of posting in this forum, as enunciated at:

READ BEFORE POSTING

Please share your work/thoughts about this assignment

If I were to do the problem - I would calculate the "unit digit" of (2018)^(2018)
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
4,334
Here is a hint:

\(\displaystyle 2018 = 20 * 10^2 + 18 \implies 2018^{2018} = \sum_{j=0}^{2018} \dbinom{2018}{j} * (20 * 10^2)^{(2018-j)} * 18^j \implies\)

\(\displaystyle \dfrac{2018^{2018}}{20} = \left ( \sum_{j=0}^{2017} \dbinom{2018}{j} * 10^{2(2018-j)} * 18^j \right ) + \dfrac{18^{2018}}{20}.\)

But that sum is an integer and thus has no relevance to a remainder. And

\(\displaystyle 18 = (10 + 8) \implies 18^{2018} = (10 + 8)^{2018} = WHAT?\)
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
4,334
First correction to previous post

\(\displaystyle 2018 = 20 * 10^2 + 18 \implies 2018^{2018} = \sum_{j=0}^{2018} \dbinom{2018}{j} * (20 * 10^2)^{(2018-j)} * 18^j = \)

\(\displaystyle \sum_{j=0}^{2018} \dbinom{2018}{j} 20^{(2018 -j)} * 10^{\{2(2018-j)\}} * 18^j =\)

\(\displaystyle \left ( \sum_{j=0}^{2017} \dbinom{2018}{j} 20^{(2018 -j)} * 10^{\{2(2018-j)\}} * 18^j \right ) + \left \{ \dbinom{2018}{2018} * 20^0 * 10^{(2 * 0)} * 18^{2018} \right \} =\)

\(\displaystyle \left ( \sum_{j=0}^{2017} \dbinom{2018}{j} 20^{(2018 -j)} * 10^{\{2(2018-j)\}} * 18^j \right ) + 18^{2018} \implies\)

\(\displaystyle \dfrac{2018^{2018}}{20} = \left ( \sum_{j=0}^{2017} \dbinom{2018}{j} * 20^{(2017-j)} * 10^{2(2018-j)} * 18^j \right ) + \dfrac{18^{2018}}{20}.\)

Second correction is a clarification.

The sum

\(\displaystyle \left ( \sum_{j=0}^{2017} \dbinom{2018}{j} * 20^{(2017-j)} * 10^{2(2018-j)} * 18^j \right ) \)

is necessarily an integer and thus has no relevance to a remainder. Any remainder thus results from

\(\displaystyle \dfrac{18^{2018}}{20}\)
 
Last edited:

Subhotosh Khan

Super Moderator
Staff member
Joined
Jun 18, 2007
Messages
20,133
Sorry for any inconveniences but i was wondering whether anybody could be able to help me solve this arithmetic question that i found in a Maths Olympiad Textbook, the question is to be attempted without a calculator.

What is the remainder of (2018^2018)/20?

Thanks, this problem has been gnawing at me for the past few hours and sorry for any inconvenience.
2018^1 ............. unit digit ...............8

2018^2 ............. unit digit ...............4

2018^3 ............. unit digit ...............2

2018^4 ............. unit digit ...............6

2018^5 ............. unit digit ...............8

2018^6 ............. unit digit ...............4

2018^7 ............. unit digit ...............2

2018^8 ............. unit digit ...............6

2018/4 \(\displaystyle \ \to \ \ \) remainder 2

continue.....
 

mchen60

New member
Joined
Jan 11, 2020
Messages
2
Please follow the rules of posting in this forum, as enunciated at:

READ BEFORE POSTING

Please share your work/thoughts about this assignment

If I were to do the problem - I would calculate the "unit digit" of (2018)^(2018)
Oh yep sorry it is my first time posting, ill keep in this in mind in all my future posts, thankyou.

Also thanks for your help, ive tried finding the unit digit and it follows the pattern

2018^1 = ...8

2018^2 = ...16

2018^3 = ...24

2018^4 = ...32

2018^5 = ...40

8^(2018/5) ====> 8^3 = 24


Then the cycle repeats every 5th entry so you could simplify the equation to 8^(2018/5) which for finding the unit digit is the same as 8^3 and thus 24.

This then implies that the remainder is either 14 or 4 for which im a bit unsure of how to proceed
 

Subhotosh Khan

Super Moderator
Staff member
Joined
Jun 18, 2007
Messages
20,133
Oh yep sorry it is my first time posting, ill keep in this in mind in all my future posts, thankyou.

Also thanks for your help, ive tried finding the unit digit and it follows the pattern

2018^1 = ...8

2018^2 = ...16

2018^3 = ...24

2018^4 = ...32

2018^5 = ...40

8^(2018/5) ====> 8^3 = 24


Then the cycle repeats every 5th entry so you could simplify the equation to 8^(2018/5) which for finding the unit digit is the same as 8^3 and thus 24.

This then implies that the remainder is either 14 or 4 for which im a bit unsure of how to proceed
I am not sure - what you are trying to do above! Please read my response (#5) carefully - and follow through.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
6,205
Oh yep sorry it is my first time posting, ill keep in this in mind in all my future posts, thankyou.

Also thanks for your help, ive tried finding the unit digit and it follows the pattern

2018^1 = ...8
2018^2 = ...16
2018^3 = ...24
2018^4 = ...32
2018^5 = ...40
8^(2018/5) ====> 8^3 = 24

Then the cycle repeats every 5th entry so you could simplify the equation to 8^(2018/5) which for finding the unit digit is the same as 8^3 and thus 24.

This then implies that the remainder is either 14 or 4 for which im a bit unsure of how to proceed
You seem to be trying to do the right thing, but the details are all wrong. For division by 20, you do want to be keeping the last two digits (you'd only need one for division by 10), but you have to start from the beginning, and you have to do the arithmetic right. (You appear to have multiplied by 1, 2, 3, 4, 5 rather than raising to that power.)

2018^1 = 2018; the last two digits are 18, not just 8.

2018^2 is found by multiplying that by 18; keeping only the last two digits, you get 18*18 = 324, so the last digits are 24, not 16.

Now see when the remainder on division by 20 repeats.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
5,407
2018^1 ............. unit digit ...............8

2018^2 ............. unit digit ...............4

2018^3 ............. unit digit ...............2

2018^4 ............. unit digit ...............6

2018^5 ............. unit digit ...............8

2018^6 ............. unit digit ...............4

2018^7 ............. unit digit ...............2

2018^8 ............. unit digit ...............6

2018/4 \(\displaystyle \ \to \ \ \) remainder 2

continue.....
Subhotosh, I must admit that I am not getting your approach. Are you sure you are correct? If yes, then can you please explain. If not, well you know what you have to do.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
4,334
Subhotosh Khan's approach is definitely correct, but why it is correct is not immediately obvious unless you have already done similar problems. It depends on the decimal system of numeration.

The rationale is partially indicated indicated in my corrected response.

\(\displaystyle 2018 = 20 * 10^2 + 18 \text { and } 18 = 10 + 8.\)

From that, as my corrected response shows, the value of the remainder is determined by

\(\displaystyle \dfrac{18^{2018}}{20}.\)

But then it follows that the remainder is determined by

\(\displaystyle \dfrac{8^{2018}}{20}.\)

I left that for the student to show.

Now Subhotosh comes in. You can prove by induction that any positive power of 8 can be expressed as the sum of an integer evenly divisible by 20 and a units digit that is cyclic from 8 to 4 to 2 to 6 and then repeats.Thus the remainders are cyclic as well.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
4,334
Again I find that I need to clarify my previous post while still leaving something for the student to do and learn from.

First, what depends on the decimal system of numeration is the structure of one possible analysis, which happens to be the one I outlined, rather than the fact that the remainders (8^n/20) are cyclic.

Second, I have realized that the formal proof of the cyclicality indicated by SK is not itself inductive in any obvious way but can be demonstrated by first proving four lemmas of which only the first is inductive. I shall leave the last three lemmas and the theorem itself for the student. Here is the first lemma and its proof.

\(\displaystyle n \in \mathbb Z,\ n \ge 1 \implies 8^{(4n-3)} = 20j_n + 8, \text { such that } n_j \in \mathbb Z \text { and } j_n \ge 0.\)

Proof

\(\displaystyle x \in \mathbb X \implies x \in \mathbb Z,\ x \ge 1, \text { and } \exists \text { non-negative integer } j_x \text { such that } 8^{(4x-3)} = 20j_x + 8.\)

Furthermore set X is not empty because

\(\displaystyle 1 \in \mathbb Z,\ 1 \ge 1,\ j_1 = 0,\ \text { and } 8^{(4*1-3)} = 8^1 = 20j_1 + 8 \implies 1 \in \mathbb X.\)

\(\displaystyle \text {Let } k \text { be an arbitrary member of } \mathbb X.\)

\(\displaystyle k + 1 \in \mathbb Z \text { and } k + 1 \ge 0 \because \ k \in \mathbb Z \text { and } k \ge 0 \text { by hypothesis.}\)

\(\displaystyle \text {Let } j_{k+1} = 8^4j_k + 1638.\)

\(\displaystyle j_{k + 1} \in \mathbb Z \text { and } j_{k+1} \ge 0\ \because \ j_k \in \mathbb Z \text { and } j_j \ge 0 \text { by hypothesis.}\)

\(\displaystyle 8^{\{4(k+1)-3\}} = 8^{(4k + 4 - 3)} = 8^4(8^{(4k-3)}) \implies\)

\(\displaystyle 8^{\{4(k-1)-3\}} = 8^4(20j_n + 8) \ \because \ 8^{(4k-3)} = 20j_k + 8 \text { by hypothesis}.\)

\(\displaystyle \therefore 8^{\{4(k+1)-3\}} = 20 * 8^4j_k + 32768 = 20 * 8^4j_k + 32760 + 8 =\)

\(\displaystyle 20(8^4j_k) + 20(1638) + 8 = 20(8^4j_k + 1638) + 8 = 20j_{k+1} + 8.\)

\(\displaystyle \therefore \mathbb X = \mathbb Z^+.\)

I suspect this theorem is simply one case of a much more general theorem about cyclicality of low-order digits of the positive powers of all positive integers.
 
Last edited:
Top