Editing FermatsLittleTheorem
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
If you want a password, email topicsinmaths@solipsys.co.uk
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Thu Mar 28 20:28:23 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
[[[>60 !!! 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!