ppt-number-theory-fermats-theorem_(2).pptx

Fermat's theory

1. DR. ALLAN QUISMUNDO PROFESSOR DISCUSSANT MARJORIE M. ESTUITA MAT - MATH MMA 105 – NUMBER THEORY Fermat’s Theorem

2. PRIME NUMBERS PRIME FACTORIZATION RELATIVELY PRIME NUMBERS GREATEST COMMON DIVISOR FERMAT’S THEOREM FERMAT THEOREM PROOF CONTENTS

3. A little bit of History….. Pierre de Fermat (1601-1665) was a lawyer by profession and an amateur mathematician. Fermat rarely published his mathematical discoveries. It was mostly through his correspondence with other mathematicians that his work is known at all. Fermat was one the inventors of analytic geometry and produced some of the fundamental ideas of calculus. He is probably most famous for a problem that went unsolved until 1994; that the equation xn + yn = zn has no non-trivial solution when n>2.

4. A prime number is divisible only by 1 and itself. For example: {2, 3, 5, 7, 11, 13, 17, …} 1 could also be considered prime, but it’s not very useful. PRIME NUMBERS :

5. PRIME FACTORIZATION :

6. RELATIVELY PRIME NUMBERS :

7. GREATEST COMMON DIVISOR (GCD)

8. FERMAT’S THEOREM

9. Fermat’s Little T heorem is a fundamental theorem in elementary number theory, which  helps compute powers of integers modulo prime numbers . It is a special case of Euler's theorem, and is important in applications of elementary number theory, including primality testing and public-key cryptography.

10. Fermat's Little Theorem Explanation Fermat's Little Theorem is an essential concept in  number theory , particularly in the field of  modular arithmetic . It was first formulated by the French mathematician Pierre de Fermat in 1640. This theorem establishes a crucial relationship between prime numbers and modular arithmetic. It is a powerful tool for simplifying certain mathematical calculations and it is widely used in cryptography and computer science.

11. FERMAT’S THEOREM PROOF: Consider a set of positive integers less than ‘p’ : {1, 2, 3, ….., (p-1)} and multiply each element by ‘a’ and ‘modulo p’ , to get the set X = {a mod p, 2a mod p, …, (p-1)a mod p} No elements of X is zero and equal, since p doesn’t divide a. Multiplying the numbers in both sets (p and X) and taking the result mod p yields

12. a * 2a *…* (p-1)a  [1 * 2 * 3 *…* (p-1)] (mod p) Thus, on equating (p-1)! term from both the sides, since it is relatively prime to p, result becomes, An alternative form of Fermat’s Theorem is given as

13. Example: 1. What is the remainder when is divided by 7?   Solution: In Fermat’t Little Theorem, if p is a prime number and p does not divide a, then: a = 3, p = 7         3 ³¹  

14. Example: 2. What is the remainder when is divided by 7?   Solution: In Fermat’t Little Theorem, if p is a prime number and p does not divide a, then: a = 2, p = 7           2 ³⁵   2 ³⁵  

15. Example: 3. What is the remainder when is divided by 23?   Solution: In Fermat’t Little Theorem, if p is a prime number and p does not divide a, then: a = 9, p = 23         9 ⁴⁵  

16. Example: 4. What is the remainder when is divided by 41?   Solution: In Fermat’t Little Theorem, if p is a prime number and p does not divide a, then: a = 23, p = 41         23 ¹⁰⁰²   23 ¹⁰⁰²  

17. T h a n k you for Listening Have a Blessed Day