Typically olympiad stuff....

Find out the remainder of 19^{92}/92

12 Answers

66
kaymant ·

Let φ(n) be the Euler's totient function.
Then, since φ(92)=44 and gcd(19,92)=1
therefore, 1944 ≡ 1 mod 92
Hence, 1992=1988194 (1944)2 194 ≡ 194 mod 92
But 194 ≡ 49 mod 92.
Hence, 1992 ≡ 49 mod 92
So the required remainder is 49

24
eureka123 ·

everrything ahs gone over my head...[2][2]

sir can u explain ur solution or give a simpler version of it????

39
Dr.House ·

hehe , ii was guessing that was going to come form some one

but sir`s solution is the most beautiful and elegant one if u can understand it.

well wiki it , u might end up with something .( it is not so dofficult either)

24
eureka123 ·

i couldnt understand the first statement even....and wiki has made my prob worse.......[2]maybe sir has to explain it..

66
kaymant ·

I used the Euler's theorem which stated that if n is a positive integer and a be another positive integer coprime to n, then
a^{\varphi(n)}\equiv 1\mod n
Here, \varphi(n) is the Euler's totient function which gives the number of positive integers less than or equal to n which are coprime to n. For example, \varphi(10)=4, since 1, 3, 7, 9 are the integers satisfying the required condition. Note, that 1 is taken to be coprime to all integers.
The notation a\equiv b \mod n means that a-b is divisible by n. That also means that when a is divided by n, the remainder is b.

Next, I used a formula for evaluating \varphi(n). If the prime factors of n are p1, p2, ..., pk, then \varphi(n)=n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\cdots \left(1-\dfrac{1}{p_k}\right)
Also, its quite obvious that for a prime p, \varphi(p)=p-1.
Going back to the sum, we have 92 = 22 23. Hence, \varphi(92)=92\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{23}\right)=44
So, by Euler's formula, we get
19^{44}\equiv 1 \mod 92
Hence,
(19^{44})^2\equiv 1^2 \mod 92 (1)
(You can raise both sides of ≡ to the same powers)
Also, when you divide 194 by 92 you get the remainder as 49 i.e. 194 - 49 is divisible by 92. So
194 ≡ 49 mod 92.
Multiplying this with (1), we get that 19^4 19^{88}\equiv 49 \mod 92
That is, 19^{92}\equiv 49 \mod 92
So 1992 - 49 is divisible by 92. So the remainder when 1992 is divided by 92 must be 49.

341
Hari Shankar ·

Maybe it will be easier if you add this intermediate step.

19^2 = 361 \equiv -7 \bmod 92

\therefore 19^4 \equiv (-7)^2 \equiv 49 \bmod 92

for more discussion: http://www.mathlinks.ro/viewtopic.php?p=340074#p340074

24
eureka123 ·

sir i am okay till this...
1992≡194mod(92)

but how did this come??
1992≡49mod(92)

couldnet understand from all 3 posts of sirs...

66
kaymant ·

congruence is transitive (in fact, its an equivalence relation):
a ≡ b mod m
and
b ≡ c mod m
implies
a ≡ c mod m

In post #7, you can see that 194 ≡ 49 mod 92. And already 1992 ≡ 194 mod 92.
So now it should be obvious.

3
iitimcomin ·

is there any way to answer it without knowing congruencies

24
eureka123 ·

hmmm thans sir

24
eureka123 ·

@ sharman....chinese remainder theorm can also be used here .......if u dont know congurencies..........same situation was with me 3 days back[1][1]

1
Riju ·

I am having some trouble, not learnt number theory..............

Your Answer

Close [X]