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?