24Nice
A continuation of what b555 started, I'm posting here another theorem namely the Totient theorem or the famous "EULER'S-PHI-FUNCTION-FORMULA" to ease the mod-bashings....beleive me this is another tool to ease rem calculations for JEE purpose - there are many other theorems for calculating remainders like CRT - but for JEE the totient theorem is enough......
The Theorem
"For integers 'a' & 'p' where g.c.d(a,p)=1
a^{\phi(p)}\equiv 1(modp)"
What does phi represent...
The phi function represents the number of primes before an integer that are relatively prime to it.....
Like 4....\phi (4)=2
How to calculate phi....
Factorise the number whose phi is needed in primes....Keep in mind that the phi function is multiplicative.....
\phi (a^b.c^d)=(a^b-a^{b-1})(c^d-c^{d-1})
'a' and 'c' are primes....Get it?
BTW did u notice fermat's little theorem is actually a special case of Euler's totient theorem!
-
UP 0 DOWN 0 5 6
6 Answers
62Yup..
Great work.. (I was underestimating most of you.. I mean i thought of giving it once.. but then I felt may be it would be a bit too much for many of you!)
24Practical use of this theorm::
(No releavance with JEE ofcourse)
Euler’s theorem is widely used in cryptography. The encryption scheme used nowadays,
called the RSA algorithm, works as follows:
A merchant wants to obtain the credit card number of a customer over the Internet.
The information traveling between the two can be viewed by anyone. The merchant is in
possession of two large prime numbers p and q. It transmits to the customer the product
n = pq and a positive integer k coprime to φ(n) = (p − 1)(q − 1). The customer
raises the credit card number α to the kth power, then reduces it modulo n and transmits
the answer β to the merchant. Using the Euclidean algorithm for the greatest common
divisor, the merchant determines positive integers m and a satisfying
mk − a(p − 1)(q − 1) = 1.
Then he computes the residue of βm modulo n. By Euler’s theorem,
βm ≡ αmk = αa(p−1)(q−1)+1 = α(p−1)(q−1)a · α = αφ(n)a · α ≡ α (mod n).
For n sufficiently large, the residue class of α modulo n is α itself. The merchant was
able to retrieve the credit card number.
As of this date there is no known algorithm for factoring numbers in polynomial time,
while large primes can be found relatively quickly, and for this reason an eavesdropper
cannot determine p and q from n in a reasonable amount of time, and hence cannot break
the encryption.
11LOL, so those giving credit-card nos, must be expert Number-Theorists!!!!
62yup they are..
the whole maths of cryptography is based on extremely large prime numbers...
even if the hacker has very high computation abilities (in terms of the computers he has), these large primes prevent them from hacking in for months!