Scribd
Upload
5 views1 page

Modulo Arithmetic and Remainder Theory

1) Euler's theorem states that if two numbers M and N are relatively prime (have no common factors), the remainder when M^φ(N) is divided by N is 1, where φ(N) is Euler's totient function. 2) Fermat's little theorem states that if N is a prime number and M and N are relatively prime, the remainder when M^N-1 is divided by N is 1. 3) Wilson's theorem states that if p is a prime number, the remainder when (p-1)! + 1 is divided by p is 0, meaning (p-1)! + 1 is divisible by p.

Uploaded by

Gaurav Bansal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views1 page

Modulo Arithmetic and Remainder Theory

1) Euler's theorem states that if two numbers M and N are relatively prime (have no common factors), the remainder when M^φ(N) is divided by N is 1, where φ(N) is Euler's totient function. 2) Fermat's little theorem states that if N is a prime number and M and N are relatively prime, the remainder when M^N-1 is divided by N is 1. 3) Wilson's theorem states that if p is a prime number, the remainder when (p-1)! + 1 is divided by p is 0, meaning (p-1)! + 1 is divisible by p.

Uploaded by

Gaurav Bansal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Modulo Arithmetic & Remainder Theory

Eulers Theorem If M and N are two numbers co-prime to each other ,i.e. HCF(M,N) =1 and N = [Link] , Remainder [M(N)]/ N= 1where ( ) ( )( )( ) and is known as Eulers totient function .(N) is also the number of numbers less than and prime to N
[Link] the remainder when 537 is divided by 63 Sol: 5 and 63 are co-prime to each other, therefore we can apply Eulers theorem 63= 7 * 32 z(63)=63(1-1/7)(1-1/3) 18 Therefore, Remainder [518]/63 =1 Remainder [536]/63 =1 Remainder [536] *5/63 = 5 [Link] the last three digits of 57802 Sol: To solve this type of question divide the no by 1000 1000= 53 *23 z(1000)1000(1-1/2)(1-1/5)400 Remainder 57400 /1000 =1 Remainder 57800 * 572 /1000 =549

Fermats Little Theorem If N is prime no in the above Eulers theorem ,( ) ( ) =N-1 , If M and N are two numbers co-prime to each other and N is the prime no.,Remainder [MN-1]/ N= 1
[Link] remainder 5260/31 Sol: 31 is prime no. Therefore , 5230/31=15260/31=1 Wilsons Theorem If p is a prime no .then Remainder [(p-1)!+1]/p =0 In other word (p-1)! +1 is divisible by p if p is a prime no. It also means that the remainder when (p-1)! Is divided by p is p-1where p is prime Q. Remainder 40!/41 Sol: Remainder 40!/41=41-1= 40

You might also like