Euler-Fermat theorem.pptx
- 1. Euler-Fermat theorem Dr. Kuparala Venkata Vidyasagar Lecturer in Mathematics SVLNS Govt. Degree College, Bheemunipatnam
- 2. LEARNING OUTCOMES ?Fermat¡¯s theorem ?Corollary ON Fermat¡¯s theorem ?Set of residues modulo ? ?Reduced set of residues modulo ? ?Theorems based on residue modulo m ?Euler's theorem or Euler's generalization of Fermat's theorem ?Fermat's theorem from Euler's theorem ?Examples
- 3. Fermat¡¯s theorem Statement: If. ? is a prime and (?, ?) = 1 then ???1 ¡Ô 1 mod? proof. Given that ? is a prime and (?, ?) = 1 claim: ???1 ¡Ô 1(mod?) Since (?, ?) = 1 By known theorem When the numbers ?, 2?, 3? ¡ (? ? 1)? are derided by p, remainders are 1,2,3,¡.. p-1 not necessarily in this order ??? ? ¡Ô ?1(mod?) 2? ¡Ô ?2(mod?) (? ? 1)? ¡Ô ???1(mod?) But ?1, ?2; ???1 are also remainders obtained by dividing ?, 2?, ? (? ? 1)? by ? ¡à ?1, ?2, ? ???1 ¡Ô 1 ? 2 ? 3 ? (? ? 1) ? (1) From the above congruent relations
- 4. But ?1, ?2; ???1 are also remainders obtained by dividing ?, 2?, ? (? ? 1)? by ? ¡à ?1, ?2, ? ???1 ¡Ô 1 ? 2 ? 3 ? (? ? 1) ? (1) From the above congruent relations (? ? 1)! ???1 ¡Ô (? ? 1)! (modp) Since, ? is prime (?, 1) = 1, (?, 2) = 1 ¡ (?, ? ? 1) = 1 ? (?, (? ? 1)!) = 1 ??1 ¡Ô 1(mod?) Hence the proof
- 5. If ? is a prime and a is any integer then ?? ¡Ô ?(mod?) Case (i). Let (?, ?) ¡Ù 1 ? ? ¨O ? and ? ¡Ô 0 mod? ????? ?? ¡Ô 0(mod?) and 0 ¡Ô ?(mod?) By Transitive property ?? ¡Ô ? ??? ? case(ii): Let (?, ?) = 1 By Fermat's theorem ???1 ¡Ô 1(mod?) ?? ? 1 ? ¡Ô 1(mod?) ?? ¡Ô ?(mod?) Hence the proof ¡ú If ? is prime and (?, ?) = 1 then ???1 ? 1 = ?(?)
- 6. Definition1.: A Set of integers ?0, ?1, ?2, ? ???1 is called a set of residues modulo ? if each ??(? = 0,1,2, ? ? ? 1) belongs to one and only one residue class modulo. Definition2.: A Set of integers ?1, ?2 ¡ , ???) is called a reduced set of residues modulo ? if exactly one of them, lies in each, residue class relatively prime to ?, Eg: {1,5} is a reduced set of residues modulo 6 = {0,1,2,3,4,5} (¡ß (1,6) = 1, (5; 6) = 1) ¡ú ?(?) is the number of elements in every reduced Set of residues modulo ?.
- 7. THEOREM: If ?1, ?2, ¡ ??(?), is a set of reduced residue modulo ? and (?, ?) = 1 then ??1, ??2, ¡ ???(?) is also a set of reduced residue modulo ?. Given that ?1, ?2, ¡ ??(?) is a set of reduced residue modulo ? and (?, ?) = 1 The set ??1, ??2, ¡ ???(?,} ??? ?(?) elements Since ?1, ?2, ¡ ??(?}, is a reduced Set of residues modulo ?. ? Each ??(? = 1,2, ¡ ? ?(?)) is relatively prime to ? i.e. ??, ? = 1 for ? = 1,2 ¡ ?(?) Since ?, ? = 1, ??, ? = 1 ? ??? , ? = 1 for ? = 1,2, ¡ ?(?) ¡à Each a?? is relatively prime to ? Suppose two of the numbers ??? , ??? are Congruent ??? ¡Ô ?? ?(mod?) ? ?? ¡Ô ? ?(mod?) (¡ß (?, ?) = 1) This is impossible ¡ß ??, ?? are two members of reduced Set of residues modulo m {they are incongruent) no two elements a??, a? ? are congruent Hence ??1, ??2, ¡ ar ?(?1 is also reduced set of residues modulo m.
- 8. Euler's theorem (Euler's generalization of Fermat's theorem) Statement: If (?, ?) = 1 then ? ¡Ô ?(?) 1(mod?) Proof: Given that (?, ?) = 1 Claim: ? ¡Ô ?(?) 1(mod?) Let ?1, ?2, ¡ ??(?,? be a reduced set of residues modulo ? Since(?, ?) = 1, By known theorem ??, ??2, ¡ ar?(?} is also reduced set of residues modulo ?. ¡à Each a?i is congruent modulo ? to one and only one ?? ??? ??1 ¡Ô ?1(modm) ??2 ¡Ô ?2(modm) ???? ? ???(?) ¡Ô ??(?)(modm) Multiplying the above congruence ??1, ??2 ¡ ???(?) ¡Ô ?1 ? ?2 ? ??(?)(modm) ? ?1 ? ?2 ? ?? ? ? a^?(?) ¡Ô ?1 ? ?2 ¡ ??(?(modm) ? ?1 ? ?2 ¡ ?? ? a^?(?) ¡Ô ?1?2 ¡ ??(?)(modm) ¡ß ?1, ?2; ??(?), are precisely numbers ?1 ? ?2 ¡ ??(?) ? a ¡Ô ?(?) 1(mod ?) ¡ß ?1, ?2 ¡ ?? ? , 1 = 1 Hence the proof
- 9. Derive Fermat's theorem from Euler's theorem corollary: If ? = ? and ? ¡Ô ?(?) (mod?) Then ???1 ¡Ô 1(mod?) proof: If ? = ? is a prime ?(?) = ? ? 1 Since ? ?(?) ¡Ô 1(modp)(?? Euler's theorem) ? ???1 ¡Ô 1(mod?) Hence the proof
- 10. Question: What is the last digit in the ordinary decimal representation of 3400 ? Solution: The last digit in the ordinary decimal representation of 3400 is the remainders when 3400 is divided by 10 By division algorithm 3400 ¡Ô 10q + ? where q, ? ¡Ê ? and 0 ? ? < 10 ¡à ? is the last digit such that 3400 = 10q + ? 3400 ¡Ô ?(mod10) We have to find ? such that 3400 ¡Ô ?(mod10) Since 5 is prime (3,5) = 1 By Fermat's theorem 35?1 ¡Ô 1(mod5) 34 ¡Ô 1(mod5) ? (1) Since 2 is prime and (3,2) = 1 By fermat' theorem 32?1 ¡Ô 1(mod2) 31 ¡Ô 1(mod2) 34 ¡Ô 14(mod2) ? (2) From (1) & (2) , 34 ¡Ô 1 (mod of L.C.M of 5,2 ) ) 34 ¡Ô 1(mod 10 34 100 ¡Ô 1100 (mod10) 3400 ¡Ô 1(mod10) ? = 1 Hence the last digit =1.