Last two digits mod 100 problem

[timetraveller123]

Homework Statement

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

Homework 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

The Attempt at a Solution

typically this kind on question i would solve it like say

19⁴⁰ ≡ 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

 

[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.

 

[timetraveller123]

um this is olympaid question with no calculator

 

[haruspex]

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

 

[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)$.]

 

[haruspex]

try considering 19=(20−1)

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 %).

 

[Fightfish]

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

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).

 

[haruspex]

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).

Fair enough.

 

[timetraveller123]

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

 

[haruspex]

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

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

 

[timetraveller123]

well
20² ≡ 0 mod 100
subsequently for n ≥2
20ⁿ ≡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

19^k ≡ 20k -1 mod 100

then how to proceed if this is correct

 

[ehild]

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

 

[haruspex]

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

No. It is 19^(17(15..., not ((19¹⁷)¹⁵...)

 

[haruspex]

well
20² ≡ 0 mod 100
subsequently for n ≥2
20ⁿ ≡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

19^k ≡ 20k -1 mod 100

then how to proceed if this is correct

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)?

 

[ehild]

19^k ≡ 20k -1 mod 100

then how to proceed if this is correct

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 19¹⁷=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.

 

[timetraveller123]

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)?

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?

 

[timetraveller123]

can some one explain to me because i kind of don't understand what i myself am doing

19^k ≡ 20k -1 mod 100
this means when 19^k 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
20²≡ 0 mod 100

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

 

[haruspex]

isn't 20@17 mod 100 ≡0

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

 

[ehild]

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

20k -1 mod 100 ≡ -1 mod 100

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

 

[timetraveller123]

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

so
19^k ≡ 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 20² 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?

 

[haruspex]

final remainder of 59 mod 100

Well done.

 

[timetraveller123]

well this is the given method while the answer is the same i don't 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= 17^b ≡ 17^-1 ≡ 33 mod 40

then 19^a ≡ 19³³ ≡ 59 mod 100

i understand little bit

why 17^-1 ≡ 33 mod 40

then
why is 19^a ≡ 19³³ mod 40

 

[haruspex]

why 17^-1 ≡ 33 mod 40

Because 17$\times$33≡ 1 mod 40.

why is 19^a ≡ 19³³ 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.

 

[timetraveller123]

Because 17××\times33≡ 1 mod 40.

is it about multiplicative inverses

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.

i am afraid i still don't understand

 

[haruspex]

is it about multiplicative inverses

Yes.

I would first reduce the preceding statement to a≡3 mod 5.

The expression has been reduced to 19^17-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 19^5k+3 mod 100 ≡ (20-1)^5k+3 mod 100 ≡ 20(5k+3)-1 ≡ 59.

 

[timetraveller123]

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.
now i get it thanks for the help

 

[timetraveller123]

just a quick proving could you help? thanks.so writing as polynomial
$\begin{equation} p(x) = \sum_{i =0}^{n}{a_i x^i} \end{equation}$
then by the given equation
a₀ =1999
and
$\begin{equation} 0 = \sum_{i =1}^{n}{a_i } \end{equation}$
rewriting it
$p(x) = a_n \sum_{i = 1}^{n}{\frac{a_i}{a_n} x^i} + \frac{1999}{a_n}$
now i hope to be able to prove using contradiction
how can i do it?

 

[haruspex]

just a quick proving could you help? thanks.so writing as polynomial
$\begin{equation} p(x) = \sum_{i =0}^{n}{a_i x^i} \end{equation}$
then by the given equation
a₀ =1999
and
$\begin{equation} 0 = \sum_{i =1}^{n}{a_i } \end{equation}$
rewriting it
$p(x) = a_n \sum_{i = 1}^{n}{\frac{a_i}{a_n} x^i} + \frac{1999}{a_n}$
now i hope to be able to prove using contradiction
how can i do it?

Please post as a new thread - forum rules.

 

[timetraveller123]

ok