Find the remainder when 25^18 is divided by 9

hi, can you tell about euler theorem, What i know is
E(z)=z∗[1–1/P]∗[1–1/Q], where P and Q are prime factors of denominator
do we need 1 factor or 2 prime factors. In case we don't have 2 prime factors, Is 1 prime factor ok

25^18/9 =
(18+7)^18/ 9 =
7^18 > 49^9 =
(45 + 4)^9 =
4^9 = 64^3 =
(63 + 1)^3
1^3 = 1
1/9 = r1

A method which can be used in such a case is using cyclicity of remainders. In this we see how many cycles are required to get a remainder of 1.

Interestingly, if you get a remainder of -1, then the double of the cycles gives a remainder of 1.

We get a remainder of -1, if the remainder is 1 less than the divisor (eg, 31 divided by 8 gives a remainder of 7 which is also -1)

We stop the cycle, when we get a remainder of 1 or 8. If we get a remainder of 8, then double that cycle will give a remainder of 1.

\(R[\frac{(25)^{18}}{9}] = R[\frac{5^{36}}{9}]\)


Cycle 1: \(R[\frac{5}{9}] = 5\)

Cycle 2: We multiply the remainder of the previous cycle by 5 and get the next remainder. \(R[\frac{5 * 5}{9}] = R[\frac{25}{9}] = 7\)

Cycle 3: \(R[\frac{5 * 7}{9}] = R[\frac{35}{9}] = 8 \space or -1\)

Therefore, we shall get a remainder of 1 in the 6th cycle. This means that the remainder for every 6 powers of 5 divided by 9 = 1


\(R[\frac{5^6}{9}] = 1\)


Therefore \(R[\frac{5^{36}}{9}] = R[\frac{(5^6)^6}{9}] = R[\frac{1}{9}] = 1\)



Option A

Arun Kumar

Concept 1: we can 'SPLIT' the Dividend and Multiply the Remainders, removing any Excess Remainders at the end by continually Dividing by the Divisor = 9


Concept 2: The Divisibility and Remainder Rule for 9:
if the Digits Sum to = 9k -------- # is Divisible by 9
if the Digits Sum to = 9k + 1 --------- Rem is +1 when Divided by 9
if the Digits Sum to = 9k + 2 ------- Rem is +2 when Divided by 9

***where k = NON Negative Integer


(1st) Re-write the Divisor/NUM

(25)^18 /9 -----> (25^2)^9 /9 -------> (625)^9 /9

(625)^9 /9 ----> Remainder of = ?


(2nd) Multiply the Remainders after "SPLITTING" the Exponential Term in the Dividend/NUM

[ (625)^9 /9 ] Rem of = (625/9)Rem of * (625/9)Rem of * (625/9)Rem of * (625/9)Rem of .......Multiplied 9 TIMES


Each "Part" Remainder of is ----> (625/9) Rem of ----> which yields the following Remainder:

6 + 2 + 5 = 13 = 9k + 4 ------> which means 625 when Divided by 9 yields a Remainder = +4


Excess Remainder = (4)^9 / 9


(3rd)Remove the Excess Remainder by finding a way to re-write the Dividend/NUM in terms of an Expression that is +1 or -1 away from a Multiple of 9

SPOT: (4)^3 = 64

64 = 63 + 1 ------- which is +1 MORE than the Multiple of 9 = 63


(4)^9 /9 ----> Rem of = ?

[(4)^3 * (4)^3 * (4)^3 ] / 9 ----> Rem of =

( 4^3 / 9)Rem of * ( 4^3 /9) Rem of * ( 4^3 /9) Rem of =

(64 / 9)Rem of * (64 / 9)Rem of * (64 / 9) Rem of =


EACH "Part" Remainder being Multiplied =

(63 + 1) / 9 ---> Remainder of = the same as -----> (+1) / 9 = Remainder of 1

1 * 1 * 1 = Remainder of 1

-A-

625/9 = Rem 4

Thus we have 4^9/9 = 64^3/9 = Remainder 1, Answer is clean (A) 1

Can someone please help me with this question.

I am doing everything as told above but my cyclicity of 2^18/9 is of 4.
and when im diving 18/4 = 2, which leaves it's unit digit to be 4 and not 8 as told above.

Thank you for this amazing approach!
I have never seen this kind of creative approach before👍

Posted from my mobile device

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.