The Notebook
İstanbul, Turkey

# Fermat’s Little Theorem

A French lawyer at the Parlement of Toulouse, and amateur (means lover of) Mathematician in 17th century, called Pierre de Fermat proposed the following statement:
If p is a prime number, then for any integer n, the number n^{p} − n is an integer multiple of p
This post is dedicated to provide the proof of statement
• Case 1: p is the divisor of n. Lets assume n = pk since \frac{n^p - n}{p} = \frac{n(p-1)}{p} = k(p - 1)
• Case 2: p is not the divisor of n, which indirectly means p and n are relatively prime numbers. We provide the proof with the help of numbers n.2n.3n.4n.\dots (p-1)n

Here the key point is :

r_1 = \bmod(n,p)

r_{2} = \bmod(2n,p)

\dots

r_{p-1} = \bmod(n(p-1),p)

All of these reminders, which are r_{1}, r_{2} \dots r_{p-1} equals to different values.

The reason is quite straightforward! Since n and p are relatively numbers, multiple of n, -which is less than p and represented by A- can not provide this equation: An = pB for integer B. Let's try to prove this claim as well. If we can show that equation An = pB \rightarrow \frac{A}{B} = \frac{p}{n} does not hold, it contradicts and our claim would be proved by well-known method, called contradiction.

Here is the point: since p and n are relatively prime numbers, they don't have any common divisor. On the other hand, since A is less than p by problem definition, they must have one to satisfy this equation, nevermore there is no. So, equation contradicts and now we are sure that, we can not get same reminder of p for numbers k.n and k.n + A.n -where A is less than p.

After this proof, we need to keep going on. Before that, please notice that set of [r_{1}, r_{2}, r_{3}, \dots r_{p-1}] is equivalent to set of [0, 1, 2 \dots p-1], since each of those reminders has to be unique as we proved by contradiction.

Here we go. The sign " x | y " means that "x divides y".

n = p.k_{1} + r_{1} \rightarrow p | (n - r_{1})

2n = p.k_{2} + r_{2} \rightarrow p | (2n - r_{2})

3n = p.k_{3} + r_{3} \rightarrow p | (3n - r_{3})

\dots

(p-1)n = p.k_{p-1} + r_{p-1} \rightarrow p | ( (p-1)n - r_{p-1})

Small Theorem
Let a, b, c, d and p are integers such that, p | (a - b) and p | (c - d). Then, p | (ac - bd)

Small Proof
Since we have ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d), small proof is complete.

to the end...
Here, we use this small proof to conclude Fermat's Little Theorem.

Since p | n - r_{1} and p |2n - r_{2} we can say that:

p | [n . 2n - r_1 . r_2] \rightarrow p | [2n^{2} - r_{1}r_{2}]

Here, we can also include 3n - r_3 with our new value, since p divides both of them:

p | [3n . 2n^{2} - r_{3} . r_{2} . r_{1}]

\dots

As you can realize, we can add all numbers up to (n - 1)p

p | [n . 2n . 3n \dots (p - 1)n - r_1 . r_2 . r_3 \cdots r_{p-1}]

\rightarrow p | [(p - 1)!n^{p-1} - r_{1} . r_{2} . \cdots r_{p-1}]

\rightarrow p | [(p - 1)!n^{p-1} - (p - 1)!]

\rightarrow p | [(p - 1)! (n^{p-1} - 1)]

\rightarrow p | [1 . 2 . 3 \dots (p - 1) . (n^{p-1} - 1)]

Since p is a prime number and it is not divisible with numbers in between [1, p-1], it has to be divisor of n^{p-1} - 1 which concludes the proof.

p | (n^{p-1} - 1) \rightarrow p | (n^{p} - p)

References:
{"ft_lang_label":"__label__en","ft_lang_prob":0.81519395,"math_prob":0.99963534,"size":3243,"snap":"2019-51-2020-05","text_gpt3_token_len":1162,"char_repetition_ratio":0.12627354,"word_repetition_ratio":0.02607362,"special_character_ratio":0.382362,"punctuation_ratio":0.13341969,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999478,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-21T02:05:04Z\",\"WARC-Record-ID\":\"<urn:uuid:690013ad-c19e-4132-9570-42f926e4102c>\",\"Content-Length\":\"10094\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d0ab6293-b1db-484e-8878-a08dc5e8a9e2>\",\"WARC-Concurrent-To\":\"<urn:uuid:9340ccd4-9d42-40ec-8232-9d70b18c0e48>\",\"WARC-IP-Address\":\"185.199.111.153\",\"WARC-Target-URI\":\"http://kivanccakmak.com/posts/math/fermats_little/fermats_little.html\",\"WARC-Payload-Digest\":\"sha1:K557XU2YORUK4NJZ36CI4RYZBFAUYEFT\",\"WARC-Block-Digest\":\"sha1:O6QEORIAAWVR2FL35M2XP5DURFT2VTO5\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250601241.42_warc_CC-MAIN-20200121014531-20200121043531-00338.warc.gz\"}"}