# Homework Help: Last two digits mod 100 problem

1. May 29, 2017

### vishnu 73

1. The problem statement, all variables and given/known data

the question requires you to find the last two digits of x

2. Relevant equations
φ(n) = n * (Σ (1 - 1/p) ) where p are the distinct prime factors of n the totient function

gcd(a ,n) = 1

aφ(n)≡ 1 mod n

3. The attempt at a solution
typically this kind on question i would solve it like say

1940 ≡ 1 mod(100)

but here the exponent is not a simple multiple of 40 or near multiples of 40 then how am i supposed to do this

2. May 29, 2017

### rcgldr

What is the order of evaluation, right to left or left to right? Either way, the problem could be solved with a program that uses repeated squaring to raise a number to a power modulo 100.

3. May 29, 2017

### vishnu 73

um this is olympaid question with no calculator

4. May 30, 2017

### haruspex

I would start at the bottom. What can you do with 19k mod 100?

5. May 30, 2017

### Fightfish

While studying the repetition period of the powers is a possible method, it can still get rather tedious (especially if you need to do it by hand in a time limited situation).

Another method is to try considering $19 = (20-1)$ and performing a binomial expansion of the expression. The modulo arithmetic kills off most of the terms in the expansion.
[Subsequent hint is to next decompose $17 = \left(15 + 2 \right)$.]

6. May 31, 2017

### haruspex

Yes, that's what I was hinting at in post #4.

Also, I suggest a convenient notation will make the writing out easier. I wrote @19=19@17, etc., and used % for modulo. Thus, the question is expressed as @19%100 (@ takes precedence over %).

7. May 31, 2017

### Fightfish

Ah okay, I was wondering whether you meant that or to look for the repetition cycles (the latter of which I actually tried, and its, well, not that bad I guess).

8. May 31, 2017

### haruspex

Fair enough.

9. May 31, 2017

### vishnu 73

@haruspex
19k mod 100 oscillates between 9 and 1 depending on whether k is odd or even respectively

10. May 31, 2017

### haruspex

No, that would be mod 10. Use @Fightfish's stronger hint, the binomial expansion of (20-1)k.

11. May 31, 2017

### vishnu 73

well
202 ≡ 0 mod 100
subsequently for n ≥2
20n ≡0 mod 100

then only the last two terms in the binomial expansion survive
(20 -1)k mod 100= k (20) (-1)k-1 + (-1)k mod 100
since k is odd here

19k ≡ 20k -1 mod 100

then how to proceed if this is correct

12. May 31, 2017

### ehild

Starting with the first power, k=17, that is, 1917=20*17-1 mod 100. Now raise it to the 15th power. (hint: 17=20-3).

Last edited: May 31, 2017
13. May 31, 2017

### haruspex

No. It is 19(17(15..., not ((1917)15...)

14. May 31, 2017

### haruspex

Right, so using my notation we have @19%100=(20@17-1)%100=20@17%100-1 (yes?).
Can you take the 20 out as a factor, i.e. write 20k mod 100 (=20@17%100) as 20(some expression)?

15. Jun 4, 2017

### ehild

$$17^{15^{13^{11^{9^{7^{5^{3^{1}}}}}}}}=17^M$$, the right side is 19 on some power of 17.
You got $19^k=20k-1$. For k=17, $19^k=20*17-1$. Following @haruspex's hint write 17=20-3 , so 1917=20*(20-3) - 1 = - 61 mod 100 or 39 mod 100. Raise 39 mod 100 to the 17th power again, and again, and find the period of the repetition cycle.

16. Jun 5, 2017

### vishnu 73

sorry for the late reply in overseas

19@17 ≡ 20@17 -1 mod 100

isn't 20@17 mod 100 ≡0
then isn't 20@17 -1 mod 100 ≡ -1
what is happening?

17. Jun 5, 2017

### vishnu 73

can some one explain to me because i kind of dont understand what i myself am doing

19k ≡ 20k -1 mod 100
this means when 19k is divided by 100 you get 20k -1 as remainder

but 20 k -1 can be bigger than hundred itself
so once again taking mod 100
since k = @17 bigger than 2
202≡ 0 mod 100

20k -1 mod 100 ≡ -1 mod 100
i am doing something terribly wrong what is it? point out to me?

18. Jun 5, 2017

### haruspex

No. Perhaps my notation is too confusing. 20@17 stands for 20 times @17, i.e. 20 times 171513..., not 20@17.

19. Jun 5, 2017

### ehild

Power is not product. If k is odd, 203=0 mod 100, but 20*3=60 mod 100, 20*5=0 mod 100, 20*7 =40 mod 100....

20. Jun 5, 2017

### vishnu 73

oh ya sorry i got confused with power and product there i reworked tell me if this correct thanks

so
19k ≡ 20k -1 mod 100

19@17 ≡ 20 @17 -1 mod 100

20@17 -1 mod 100 = 20@(20-3) -1 mod 100

20@(20-3) - 1 = 20 * (20 -3)m -1 where m is a positive integer

so every term but the last term in the binomial is killed because it has at least a 202 term in it the remaining modulo congruence can be written as

20*(-3)@15 -1 mod 100
now since 20 * k mod 100 has a repetition of 5 we only need to consider (-3)@15 mod 5

this is a cycle of
-3 , 4 ,-2 , 1 or 2,4,3,1

now we need to find @15 mod 4 = 15@13 mod 4 = (16 - 1)@13 mod 4 ≡ (-1) @13 mod 4

now since @13 is odd it gives a remainder of -1 or 3

so @15 mod4 ≡ 3
so 20(3) -1 to give a final remainder of 59 mod 100
is this correct?

21. Jun 5, 2017

### haruspex

Well done.

22. Jun 5, 2017

### vishnu 73

well this is the given method while the answer is the same i dont get the method can someone explain to me

let a = @17 and b = @15 . since @13 is odd b = -1 mod 16
then considering the totient function
φ(100) = 40 φ(40) = 16
by euler theorem:
a= 17b ≡ 17-1 ≡ 33 mod 40

then 19a ≡ 1933 ≡ 59 mod 100

i understand little bit

why 17-1 ≡ 33 mod 40

then
why is 19a ≡ 1933 mod 40

23. Jun 5, 2017

### haruspex

Because 17$\times$33≡ 1 mod 40.
Mod 100, not mod 40.
This is easily shown using 19=20-1. I would first reduce the preceding statement to a≡3 mod 5.

24. Jun 5, 2017

### vishnu 73

i am afraid i still dont understand

25. Jun 5, 2017

### haruspex

Yes.
The expression has been reduced to 1917-1 mod 100.
We have 17-1 ≡ 33 mod 40, but we do not need all that detail. It is enough that 17-1 ≡ 3 mod 5.
so it comes down to 195k+3 mod 100 ≡ (20-1)5k+3 mod 100 ≡ 20(5k+3)-1 ≡ 59.