This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Using Euler's Theorem does not guarantee that for gcd(a, m) = 1. Consider a = 2 modulo 7. By Euler's Theorem, 2^6 is congruent to 1 modulo 7. But, the smallest exponent that satisifes the congruence is 3. Would you mind to explain why is the order 100? I solved the problem. (with the help of bashing, not believing at Euler's Theorem at first sight)
Log in to reply
Yes, Euler's Totient function simply shows us a multiple of the order of a modulo n , g cd ( a , n ) = 1 . Since g cd ( 2 , 1 0 1 ) = 1 and ϕ ( 1 0 1 ) = 1 0 0 , we have that 1 0 0 = s k , where s ∈ N > 0 is the order of 2 modulo 1 0 1 and k ∈ N > 0 is a quotient. Therefore, we know that the order of 2 modulo 1 0 0 is a divisor of 1 0 0 , and there are only 9 divisors of 1 0 0 , namely 1 , 2 , 4 , 5 , 1 0 , 2 0 , 2 5 , 5 0 , 1 0 0 , and finding the lowest of these that works is simple if you use a calculator (the answer is 100). Kartik's solution is incorrect.
Log in to reply
Oh!!! I initially thought I was incorrect but this was the solution that came to my mind(actually my older solution was a bit like this only, but then I thought that that is going a little bit big while we are getting the answer with this method as well, so I thought this may be right).
So, yes I am really very sorry. Can you do me a favor, please? Can you please post this as a solution so that I can delete my solution? And, yes sorry to you as well @John Ashley Capellan !!!
Log in to reply
@Kartik Sharma – Well, now that you understand the actual solution, you can edit it and write it along the lines of mine.
What does order of modulo mean? Your question is not clear. Which paper have you copied this from?? Could you elaborate????????/
Log in to reply
Hey, I am posting a better solution. Have a look at that one!
By the way now, I think it's clear. If it is not, ask me once again.
by euler's totient function we know that 2^phi(101)=1(mod101) that is, 2^100=1(mod100). But we need to make sure that there is no integer less than 100 which yields the same result. let us say that 2^x=1(mod101) where x<100 if 2^x=1(mod101) then,(2^x)^y=1(mod101) where x*y=100 so as to get the same result.Now find the factors of 100 and put them in place of x and y.You will never get 2^x=1(mod100) thus 100 is the smallest.
This problem is made to celebrate my 100 day streak which is today and which is quite a big deal for me.
Order of any number is just the smallest number for which a^n = 1 mod m and m and a are co-prime. According to Euler' theorem,
a φ ( m ) = 1 m o d m
Therefore, 2 φ ( 1 0 1 ) = 1 m o d m
Or, φ ( 1 0 1 ) = the order of 2 modulo 101.
Hence, the answer is 100 which is totient function of 101 (if you cannot understand this, ask me in the comments(Hint: 101 is prime))