Quote:
Originally Posted by mithun_sarmah
HI ,
can nyone explain the chinese theorem and eulers theorem? or if there is ny link to these explaination, plz mention it. 
thanks in advance  |
Chinese Remainder Theorem
This theorem is useful if the divisors are relatively prime. Some thing like a number when divided by 7, gives a remainder 5; when divided by 9, a remainder 2 and when divided by 11, a remainder 10. Then what is the remainder when the number is divided by 7*9*11.
If two numbers a and b are relaively prime, then there always exist two integers r and s such that ar+bs=1.
This forms the basis for applying the Chinese remainder theorem(CRT).
If N (mod a) = x (mod a)
& N (mod b) = y (mod b) , where a and b are relatively prime.
then, N (mod ab) = (ar*y +bs*x) (mod ab).
What is the remainder when (3^1001)/1001?
In the above problem 1001=7*11*13.
So, first we take 7 and 11 and apply CRT and once we get remainder with 77(7*11), we take 77 and 13 and apply CRT to get the remainder with 1001(77*13).
3^1001(mod7)=5(mod7) and 3^1001(mod11)=3(mod11).
Since gcd(7,11)=1 =>7r+11s=1=>r=-3 and s=2
So,3^1001(mod77)=(7*3*-3 + 11*5*2)mod77=47(mod77)
Also, 3^1001(mod13)= 9(mod13).
Again, since gcd(77,13)=1=>77t+13u=1=>t=-1,u=6
So,3^1001(mod1001)=(77*9*-1+13*47*6)mod1001=2973(mod1001)=971(mod1001)
Euler Totient Theorem
Let n = a1^p1 *a2^p2*...., where a1,a2... are prime numbers
E(n) = n*(1-1/a1)*(1-1/a2)*....
Suppose a and n are co-primes with each other, then a^E(n) = 1 mod n
The Euler number of n, is E=E1*E2*E3 ... ,where Ei is individual euler number for each prime factor raise to the power some number.
Let Ez =LCM(E1,E2,E3...)
Ez is called the effective euler number of n.
Supposing a and n are co-primes with each other, then as already discussed that a^E = 1 mod n; similarly a^Ez = 1 mod n.
Also, note that euler number of every prime is 1 less than that number and this lays the foundation to Fermat little theorem,a special case of Euler Totient Function.
Suppose p is a prime number and a is not a multiple of p then a^(p-1) = 1 mod p.
Note: Effective euler number is not the same as the euler number. Euler number signifies the number of coprimes less than a number while effective euler number is hypothetical but always satisfies the euler's theorem.(Just replace euler number with effective euler number)
Help
Linear Mode
