A Research on Fermat Little Theorem and Its Euler's Generalization: Selected Proofs

INTRODUCTION

Fermat's 'little' theorem is one of the gems of Number Theory, and to stamp the 400"1 commemoration of Fermat's introduction to the world, I offer this discussion. My discussion isn't proposed as a prologue to Number Theory, nor in fact even as a prologue to Maple, in spite of the fact that in the two cases it could fill in accordingly. Undoubtedly in the time accessible (somewhere in the range of 30 minutes) me will be able to cover just a little determination of the points recorded beneath. Any individual who is intrigued may get to the this Maple .mws record at my site, and furthermore a html content transformation (which might be perused by any individual who has an internet browser, and does not require having Maple); they are in the Public and Other Lectures area of the Maple segment of my website. Then again his little theorem - which was generally simple to demonstrate (however what number of could make a proof stomach muscle initio?) - has a tremendous scope of numerical results, and one noteworthy practical application. In this investigation we consider a portion of the early proofs of Fermat's Little Theorem. Our principle reference is History of the Theory of Numbers, Volume 1 by L.E. Dickson. Since a large number of the first sources to the proofs of these theorems are dark, we more often than not allude the peruser to Dickson. The grouping of the proofs shows up sequentially, so as to show how the proofs advanced all through the seventeenth twentieth hundreds of years. One of our principle objectives is to take crude, inadequate proofs laid out in Dickson and fill in the missing subtleties. We do, in any case, attempt to hold the first kind of the proofs as for documentation and phrasing. Another objective is to underscore the extraordinary assortment of strategies that were utilized to demonstrate the two theorems and their generalizations.

The - little' of the theorem: When did this theorem begin to be called 'Fermat's little theorem? Who (in English) first called it so? As a matter of fact not every person calls it so. In Vol I [1919] of Dickson's monumen¬tal three volume [.History of the] Theory of Numbers there is a whole part dedicated to 'Fermat's and Wilson's Theorems.' Hardy and Wright, Davenport, Nagell, ... , basically use 'Fermat's theorem.' And Sierpinski calls it 'Straightforward The¬orem of Fermat' in his 1964 .4 Selection of issues in the Theory of Numbers. Obviously everybody realizes what 'Wilson's theorem' is - since there is just a single such theorem (at the same time, presumably, somebody will compose and let me know of another!) - yet 'Fermat'8 theorem'? Well there are a few petitioners: the lovely result - to name however one - that each prime p. with p= 1 (mod 4), is representable by p=a-+ t? for a few (remarkable; disregarding, obviously, change of signs, and

The theorem itself : According to Dickson (and others: see Bibliography) Fermat previously declared his theorem in a letter to Mersenne, June (?), 1640. Fermat's 'little' theorem. Give p a chance to be prime, and a be any number with a 0 (mod p), at that point In non-coinciding language: let p be any prime, and a be any whole number not detachable by p. at that point leaves leftover portion 1 on division by p.

Maple examples (the meaning of each command should be clear). • restart; • p[l] := nextprime(120); • p, := 127 • a[l] := 2; • ai := 2 • 57 mod 5; # the remainder 57 leaves on division by 5

• 2

• a[l]"(p[l] - 1);

• 85070591730234615865843651857942052864

• a[l]"(p[l] - 1) mod p[l];

• 1

• p[2] := nextprime(10~20 + randO); • p2 := 100000000427419669091 • a[2] : = rand(); # Maple ha3 a 12-digit random number generator: • a2 := 321110693270 • a[2] mod p[2];

• 321110693270

• a[2]-(p[2] - 1); outcome of his investigations concerning Euclid's theorem on perfect numbers. More specifically it originated from his investigations into the question of the primality or otherwise of. On occasion we say things to our students like: I'm not sure how such- and-such first happened, was discovered, but I think it happened like this... For example, I find myself telling my students how I think Euclid could have discovered his famous theorem on perfect numbers. Also, many years ago, I used to (wrongly) tell how I thought Fermat had discovered his 'little' theorem... ; I thought he had found it by thinking about the decimal expansions of rational numbers. In Section consider decimal and other expansions, and there you will see how anyone could have formulated Fermat's little theorem had he/she simply asked the right questions having investigated decimal expansions of certain rational numbers.

Here the simple, and clear point I wish to make isn't just does Fermat's little theorem clarify, or help one to comprehend certain outstanding marvels regarding the decimal expansions of rational numbers, however that those very wonders themselves - with general bases being u»?d (and not simply decimal, for example base 10) - can lead somebody to re-finding of Fermat's little theorem. Specifically, on the off chance that one were working with youthful understudies, at that point, with appropriate direction, they could be directed to guess Fermat's little theorem. Specifically I refer to the quickly observed fact that the number of digits in the period of the decimal expansion of(where p is any prime with) appears to an imestigator to be (and may be proved using Fermat's little theorem to be): • either ( p — 1) • or a divisor of ( p — 1) Start. Many sensitive young people are fascinated (or, at least, used to be!) with phenomena like: • • ... ad infinitum

• 

• 142857 142857 ... ad infinitum [Here, and elsewhere, I make spaces to emphasise the periodic block.]

• the rational number(where m and n are positive, m < n) has a periodic decimal expansion provided n is not divisible by 2 or 5 047619 047619 (I have deliberately made spao?s to emphasise the periodic block) ... • otherwisehas an eventually periodic decimal expansion 45 45 45 45 ... (here n is divisible by 2) 054 054 054 ... (here n is divisible by 5) • Anyone who gets preoccupied with the lengths of these periodic blocks quickly makes an often made (re)discovery: for prime the length of the period of the decimal expansion ofis either ( p— 1) or a divisor of ( p— 1). A sensitive eye gets quickly drawn towards the 'prime' element in all of this because the examples with long periods - long in relation to the size of the denominator - having encountered examples like: 142857 142857 ... [period length 6]= .588235294117647©-10 588235294117647 ... [period length 16]= .5263157894736842le-1 0 52631578947368421 ... [period length 18] Anyone who knows sufficient Number Theory will know that they are primes p for which ordp( 10) = p — 1; in other words they are primes for which 10 is a primitive root [See, too. Section on open problems]. As soon as the eye has got drawn in to for p = 7, 17. 19, 23. 29, etc, then the eye returns to look at the decimal expansions of the reciprocals of the other primes (not 2 or 5), and notices: 3 3 3 3 3 ... [period length 1]= .9e-l 09 09 09 09 ... [period length 2] = ,76923e-l 076923 076923... [period length 6]= .32258064516129^1 0 32258064516129 ... [period length 15] Maple has a command for computing those periodic decimals expansions, and it'8 called 'pdexpand'. To access it one needs to load Maple's Number Theory package: • with(numtheory); Warning, new definition for M

• order(10, 7); • pdexpand(l/31);

PDEXPAND(1, 0, []. [0. 3, 2. 2. 5, 8. 0. 6, 4, 5. 1, 6, 1, 2, 9])

This is not a Maple tutorial, but anyone who wishes may consult what Maple has to say about "pdexpand" by executing the following line (first remove the and then execute): • # ?pdexpand • pdexpand(135/14);

PDEXPAND(1, 9. [6]. [4, 2, 8. 5. 7, 1])

means that= 9.6 428571 428571 428571 ... ad infinitum. and • convert(PDEXPAND(-1, 2, [1, 1], [9, 0, 1, 3]), rational); means that -2.11 9013 9013 9013 ... =

• pdexpand(l/21); PDEXPAND(1, 0, [], [0. 4, 7, 6. 1, 9]) • pdexpand(l/22); PDEXPAND(1, 0. [0], [4. 5]) • pdexpand(1/185); PDEXPAND(1. 0. |0]. [0. 5, 4]) In passing I cannot resist asking if from:= .9e-l 0909 09 ... (A) my reader can determine the decimal expansion of? In other words, what do you get if you square both sides of (A)? • pdexpand(l/ll); PDEXPAND(1, 0. 0, [0, 9]) • pdexpand(l/ll^2);

PDEXPAND(1, 0. ||, [0, 0. 8. 2, 6. 4. 4, 6. 2. 8, 0, 9.

9, 1, 7. 3, 5, 5. 3, 7, 1. 9|) And? • pdexpand(l/ll^3); A suggestion for playing. Much fun may be had by investigating (and explaining what's going on with) decimal expansions of; ... ; etc. A knowledgeable practitioner should be able to quess, and prove results. A word of warning. One must be careful about saving ones before executing some commands!! Returning to above. And now to observe the obvious connection to Fermat's little theorem. All, I believe, becomes clear from almost one reflection; simply consider the decimal expansion of, say,: 142857 142857 ... cut infinitum How does one prove that the non-terminating decimal on the right hand side is equal to the (rational) numberOf course one needs to have studied infinite series to giw a precis? meaning to such an object... It's very simple, and straightforward, providing one knows that: and thus: etc Two points, now, are simply these: • Fermat's little theorem (with p = 7, a = 10) forcesto have the decimal (10) expansion that it has. • The decimal expansion ofbeing what it is, forces Fermat's little theorem to hold for p = 7, a = 10. Why? It's simple; 1. By Fermat's little theorem, with p = 7 and a = 10, we have 106 = 1 (mod 7), and thus 7 divides ( 106 — 1). Performing the division by 7 we find that 106 - 1 = 7*142857, and so it follows that: = .142857 142857 142857 ... cut infinitum 2. If one has determined that the decimal expansion of i is given by: 142857 142857 ... ad infinitum then one hasnamely 106 - 1 =7*142857. Thus 7 divides ( 106 - 1), and so it follows that 106 = 1 (mod 7). I hardly need write any more on this?

Here I begin with a famous empirical discovery of Fermat‘s: every odd prime divisor of ( x2 + 1) leaves remainder 1 on division by 4 In the following, this is what I am doing: I first form a random x2 + 1, factor it, and then verify that

• if x is odd then one of the primes dividing x2 + 1 will be 2 itself (and it is trivial that 22 will not be a factor), otherwise all the other prime factors will be odd (and, in extremis, there might only be one: 32 + 1 = 2*5) • if x is even then all primes dividing x2 + 1 will be odd (and, in extremis, there might only be one: 22 + 1 = 5) > x := rand(); x := 343633073697 > n := x^2 + 1; n := 118083689338447833247810 > m := ifactor(n); m := (2) (5) (542340005228713697) (21773) > L := [op(m)];

L := [ (2), (5), (542340005228713697), (21773)]

> r := nops(L); # how many prime factors there are r := 4 • for k to r do • p[k] := op(L[k]) • od; p4 := 2 p2 := 5 p3 := 542340005228713697 p4 := 21773 • for k to r do • p[k] mod 4 • od; 2 1 1 1 theorem. An extension of that result is that every odd prime divisor of ( x4 + 1) leaves remainder 1 on division by 4 Here, numerical experimentation like the above (using rand()) would be problematic, since Maple - almost certainly - would have difficulty in performing the resulting factorisations (and, in fact, it is precisely the difficulty of factoring that is the basis of RSA public-key cryptography). Instead, I choose more modestly sized n's to factor: • x := randO mod 1234321; # to reduce the 3ize of 'x': x := 57094 • n := x^4 + 1; n := 10625806006435226897 • m := ifactor(n); m := (17) (718040S874809) (87049) • L := [op(m>];

L := | (17). (71804(8874809), (87049)]

• r := nops(L); # hou many prime factors there are r := 3 • for k to r do • p[k] := op(L[k]) • od; p1 := 17 p2 := 718040S874809 p3 := 87049

1

That result - re ( x4 + 1) - may be proved in the same way as the (x2 + 1) result. In general one has: every odd prime divisor of leaves remainder 1 on division by This result enables trial factoring of Fermat numbers to be eased, and there is another simple extension of it that saves a further 50%... Yet another application of Fermat's little theorem is to the trial factoring of Mersenne numbers ( Mp = 2P — 1, with p prime): Theorem. Every prime divisor q of Mp satisfies q = 1 (mod p). It is pleasing that that Theorem can be proved by using Fermat's little theorem, when it was precisely the very discovery of that theorem which led Fermat to discover his little theorem in the first instance. Comment. A great deal more about Mersenne numbers (including the Lucas- Lehmer test) is available in my 1995 Maple public lecture "The recently discovered record largest known prime," and a great deal more more about Fermat numbers (including the Pepin test) is available in my 1999 Maple public lec- ture"The history of Fermat numbers from August 1641,* both at my web site.

I have briefly hinted at the sort of use that can be made of Fermat's little theorem to establish that a number is composite, but a great deal more is involved in using it as a starting point in proving that a number is prime. I refer the interested reader to my web site, where I have many Maple worksheets - in the 2nd and 3rd year, and Public and Other Lectures sections of my site's Maple section - devoted to primality testing.

(in practical applications p and q are both large, and with some added refinements for security purposes). A fairly detailed exposition of the RSA method may be read in my Maple public lecture - Bill Clinton, Bertie Ahem, and digital signatures - in the Maple Public and Other Lectures section of my web site. The two prime version of Fermat's little theorem is simply this: let • p and q be distinct primes (in cryptographic applications they will be large, but not just merely large (as is sometimes incorrectly stated); to see why, refer to Section ) • a be any integer with(mod p) and(mod q) then One may easily give a proof of the two prime version which is independent of the normal proof of the full Fermat-Euler result.

Euler's (Ivory's?) proof of Format's little theorem : This proof relies on the simple, but powerful observation that for prime p. and integer(mod p), one has (mod p) in some order A small prime numerical demonstration: ► restart; ► p := 23; p := 23 ► a := 12; a := 12 ► seq(a*k mod p, k=l..p-l); 12. 1, 13. 2, 14. 3. 15. 4. 16. 5. 17, 6. 18, 7. 19, 8. 20, 9. 21, 10. 22, 11

18. 19, 20. 21, 22]

Then(mod p), from which it follows that (mod p). Euler's proof concerning ( x2 + 1) :

But clearly (mod p), and so by Fermat's little theorem

An easy proof of a 2-prime version of Fermat's little theorem : If one is in a hurry then this proof allows one to sidestep having to establish all the side work necessary to a proof of the full Euler-Fermat theorem; one merely has to make two applications of the standard Fermat little theorem. We have:

and thus giving Similarly since gcd(p. q) = 1. [End of proof.) As one quickly learns in RSA public-key cryptography, the 2-prime version of Fermat's 'little' theorem plays a central role.

In this lecture, we cover Fermat Little Theorem, Euler's generalization of this theorem, and end with Wilson's theorem. Fermat's Little Theorem, and Euler's theorem are two of the most important theorems of modern number theory. Since it is so fundamental, we take the time to give two proofs of Fermat's theorem: (i) the induction based proof, and (ii) the permutation based proof. The second of these generalizes to give a proof of Euler's theorem. There is a third proof using group theory, but we focus on the two more elementary proofs. One form of Fermat's Little Theorem states that if p is a prime and if a is an integer then For example divides 23 — 2 = 6 and 33 — 3 = 24 and 43 — 4 = 60 and 53 — 5 = 120. Similarly, 5 divides 25 — 2 = 30 and 35 — 3 = 240 et cetera. Obviously ap — a factors as a(ap-1 — 1). So if p \ a then we have This gives another common form of Fermat's Little Theorem. For example, divides 52 — 1 = 24 and 42 — 1 = 15 and 22 — 1 = 3. Also, 5 divides 24 — 1 = 15 and 34 — 1 = 80 and 44 — 1 = 255, and 7 divides 26 — 1 = 63 et cetera. After Gauss introduced congruences, the theorem was typically written or, equivalently,

defined as follows. Definition (Stinson) Supposeandare integers. If gcd(a,m) = 1 then we say that a and m are relatively prime. The number of integers inthat are relatively prime to m is denoted by We setThe function is called the Euler phi-function, or Euler totient function. Clearly, for m prime, we haveFurther, we state the following fact without proof, and leave the proof as an easy exercise. Fact. If m is a prime power, say, m = pe, where p is prime and p > 1, then

In this paper, we have presented an original proof of Fermat‘s Little Theorem. The significance of this proof lies in the fact that it relies only on mathematical techniques older than either the statement of the theorem by Fermat or the first proof by Euler. While the work detailed previously show how diverse the proofs of Fermat‘s Little Theorem can be, it is important to note the theorems‘ practical applications. In his text, An Introduction to Cryptography.

1. Burton, David M. (2004). Elementary Number Theory, Third Edition. Wm. C. Brown Publishers. 2. Crandall, R., Dilcher, K., Pomerance, C. (1997). A search for Wieferich and Wilson primes. Math. Comp. 66, pp. 433–449. Lerch Quotients and Primes, Fermat Wilson quotients, and the WW Primes 2, 3, 14771 ,13 3. Dickson, L.E. (1919). History of the Theory of Numbers, vol. 1. Carnegie Institution of Washington, Washington, D. C. (1919); reprinted by Dover, Mineola, NY (2005) 4. Dobson, J.B. (2011). On Lerch‘s formula for the Fermat quotient (2011, preprint); available at http://arxiv.org/abs/1103.3907 6. Glaisher, J.W.L. (1900). A congruence theorem relating to Eulerian numbers and other coefficients. Proc. Lond. Math. Soc. 32, pp. 171–198. 7. Grosswald (2004). Emil Topics from the Theory of Numbers, Second Edition. Birkauser Boston. 8. Guy, R.K. (2004). Unsolved Problems in Number Theory, 3rd ed. Springer, New York 9. Hillman, Abraham P. and Gerald L. (2004). Alexanderson Abstract Algebra A First Undergraduate Course, Fifth Edition. International Thomas Publishing. 10. Lerch, M. (1905). Zur Theorie des Fermatschen Quotienten ap−1−1 p = q(a). Math. Ann. 60, pp. 471–490. 11. Mollin, Richard A. (2001). An Introduction to Cryptography. Chapman & Hall/CRC, Boca Raton. 12. Robbins (2006). Neville Beginning Number Theory, Second Edition. Jones and Bartlett Publishers, Inc., Sudbury, MA.

Assistant Professor of Mathematics, A.I.J.H.M. College Rohtak, Haryana, India sikanderbeniwal2212@gmail.com