Editing FermatsLittleTheorem
You are currently browsing as guest..
To change this, fill in the following fields:
Username
Password
Click here to reset your password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Thu Apr 25 07:14:33 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
[[[>50 !!! Some examples: Let's use /p=7/ * EQN:2^{\small{7-1}}-1%3D2^6-1%3D64-1%3D63, a multiple of 7 * EQN:3^{\small{7-1}}-1=3^6-1=729-1=728, a multiple of 7 * EQN:4^{\small{7-1}}-1=4^6-1=4096-1=4095, a multiple of 7 Let's use /p=5/ * EQN:2^{\small{5-1}}-1=2^4-1=16-1=15, a multiple of 5 * EQN:3^{\small{5-1}}-1=3^4-1=81-1=80, a multiple of 5 * EQN:4^{\small{5-1}}-1=4^4-1=256-1=255, a multiple of 5 ]]] Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a prime number, then for any integer a, EQN:a^p-a will be evenly divisible by p. This can be expressed in the notation of modulo arithmetic as follows: EQN:a^p\equiv{a} /(mod/p)/ A variant of this theorem is stated in the following form: * If p is a prime number ** and /a/ is an integer with no factors in common with /p/ *** then EQN:a^{p-1}-{1} is a multiple of /p./ Fermat's little theorem is the basis for the Fermat primality test. Euler's extension of Fermat's little theorem is the basis of the RSA public-key cryptosystem. [[[>50 !! Page Challenge This theorem only ~works in one direction. Every prime satisfies the equation, but there are non-primes that also satisfy it. Can you find one? ]]] * If /n/ is a positive integer ** and EQN:\phi(n) is how many numbers that are *** less than /n/ and have no factors in common with /n,/ **** then if /a/ is one of those numbers, ***** then EQN:a^{\small\phi(n)}-1 is a multiple of /n./ ---- !! Proof [[[>30 This proof can be adapted to prove Euler's result by taking the product of all the numbers co-prime to /n,/ rather than using the numbers from /1/ to /p-1./ ]]] Let /p/ be a prime. What we're going to do is write down one product, and then evaluate it in two different ways. One way will give some number EQN:F, the other will give EQN:a^{p-1}F, and so these are equal. So suppose we have a number EQN:a which is between 1 and EQN:p-1 inclusive. Everything is being done modulo /p./ We start by looking at the product EQN:(p-1)! which is EQN:F=1\text{x}{2}\text{x}\ldots\text{x}(p-1). This is some number which, because we are working modulo a prime, has a multiplicative inverse, EQN:F^{-1}. [[[> In the integers modulo a prime, every number _ from 1 to /p-1/ has a multiplicative inverse. _ _ We'll use that several times. ]]] Now let's look at the product * EQN:P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p-1)a). This is the magic formula that we'll evaluate in two different ways. [[[> If EQN:ma{\equiv}na, multiplying by EQN:a^{-1} shows that EQN:m=n. _ That means that each of the terms EQN:a,~2a,~3a,~\ldots~(p-1)a _ must be different. ]]] Firstly, each of the elements here are different. The element /a/ has a multiplicative inverse, so multiplying all the number from 1 up to /p-1/ can be undone. That means we can't get the same answer twice, so they're all different. That means that the product is just the same elements multiplied in a different order, and so the product is again /*F.*/ But let's rearrange it to bring all the /a's/ to the front. Then * EQN:P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p-1)a)\quad\quad (equation 1) is the same as * EQN:P{\equiv}a^{p-1}(1)\text{x}(2)\text{x}(3)\text{x}\ldots\text{x}(p-1)\quad\quad (equation 2) Equation (1) shows that EQN:P{\equiv}F (because it's the same product in a different order) Equation (2) shows that EQN:P{\equiv}a^{p-1}F So EQN:F{\equiv}a^{p-1}F Now we can multiply by EQN:F^{-1} and we can see that EQN:1{\equiv}a^{p-1} which is the result we wanted!