BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Fermat’s Theorem | number theory

Fermat’s Theorem | number theory

Fermat’s Theorem: Let p be a prime and suppose that p ∤ a. Then ap – 1 ≡ 1(mod p)

Proof: We start by considering the first that p – 1 positive multiplies of a; that is the integers

a, 2a, 3a, …, (p – 1)a

None of this numbers is congruent to modulo p to any other, nor is any congruent to zero. Indeed, if it happen that

ra ≡ sa (mod p)             1 ≤ r < s ≤ p – 1

Then a could be cancelled to give r ≡ s (mod p), which is impossible. Therefore, the previous set of integers must be congruent modulo p to 1, 2, 3,…, p – 1 , taken in some order. Multiplying all this congrunces together, we find that

  1. 2a. 3 … (p – 1 )a ≡ 1. 2. 3 … (p – 1) (mod p)

whence

ap – 1 (p – 1) ! ≡ (p – 1) ! (mod p)

Once (p – 1) ! is cancelled from both sides of he preceding congruence , our line of reasoning cultimaes in the statement that ap – 1 ≡ 1 (mod p), which is fermat’s theorem. (Proved)

Corollary: If p is a prime, then ap ≡ a(mod p) for any integer a.

Proof: When p | a, the statement obviously holds; for in this setting, ap ≡0≡a(mod p). If p ∤ a , the according to Fermat’s theorem, we have ap – 1 ≡ a(mod p), when this congruent is multiplied by a, the conclusion ap ≡ a(mod p). (Proved)

Theorem: If n is an odd peseudoprime, then Mn = 2n – 1 is larger one.

Proof: Since n is a composite number, we can write n = rs, with1 < r ≤ s < n. Then 2r – 1 | 2n – 1 , or equivalently 2r – 1 | Mn, making Mn composite. By our hypothesis 2n ≡ 2(mod n); hence 2n – 2 = kn for some integer k. It follows that

2Mn – 1 = 22^n – 2 = 2kn

This yields

2Mn – 1= 2kn – 1

= (2n – 1 ) (2n(k – 1 ) + 2n(k – 2 ) + … + 2n + 1)

= Mn (2n(k – 1 ) + 2n(k – 2 ) + … + 2n + 1)

≡ 0 (mod Mn)

We see immediately that 2Mn – 1≡ 0(mod Mn), in light of which Mn is a peseudoprime. (Proved)

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *