Fermat's Little Theorem.

Introduction.

Prime Numbers have uses in Cryptography, important part of Computer Sciences.

Functional Paradigm uses Mathematics for Computing extensively, therefore this article.


Fermat's Little Theorem.

If p is a prime number and a is a natural number, then:

a^p≡a (mod p).

Furthermore, if p does not divide a, then there exists some smallest exponent d such that:

a^d-1≡0 (mod p)

and d divides p-1. Hence,

a^(p-1)-1≡0 (mod p).

The theorem is sometimes also simply known as 'Fermat's theorem' (Hardy and Wright 1979, p. 63).

This is a generalization of the Chinese hypothesis and a special case of Euler's totient theorem. It is sometimes called Fermat's primality test and is a necessary but not sufficient test for primality. Although it was presumably proved (but suppressed) by Fermat, the first proof was published by Euler in 1749. It is unclear when the term 'Fermat's little theorem' was first used to describe the theorem, but it was used in a German textbook by Hensel (1913) and appears in Mac Lane (1940) and Kaplansky (1945).

The theorem is easily proved using mathematical induction on a. Suppose p|a^p-a (i.e., p divides a^p-a). Then examine:

(a+1)^p-(a+1).

From the binomial theorem,



Rewriting,



But p divides the right side, so it also divides the left side. Combining with the induction hypothesis gives that p divides the sum:



as assumed, so the hypothesis is true for any a. The theorem is sometimes called Fermat's simple theorem. Wilson's theorem follows as a corollary of Fermat's little theorem.

Fermat's little theorem shows that, if p is prime, there does not exist a base a < p with (a,p)=1 such that a^(p-1)-1 possesses a nonzero residue modulo p. If such base a exists, p is therefore guaranteed to be composite. However, the lack of a nonzero residue in Fermat's little theorem does not guarantee that p is prime. The property of unambiguously certifying composite numbers while passing some primes make Fermat's little theorem a compositeness test which is sometimes called the Fermat compositeness test. A number satisfying Fermat's little theorem for some nontrivial base and which is not known to be composite is called a probable prime.

Composite numbers known as Fermat pseudoprimes (or sometimes simply 'pseudoprimes') have zero residue for some as and so are not identified as composite. Worse still, there exist numbers known as Carmichael numbers (the smallest of which is 561) which give zero residue for any choice of the base a relatively prime to p. However, Fermat's little theorem converse provides a criterion for certifying the primality of a number. A table of the smallest pseudoprimes P for the first 100 bases a follows (OEIS A007535; Beiler 1966, p. 42 with typos corrected).

2	341	22	69	42	205	62	63	82	91
3	91	23	33	43	77	63	341	83	105
4	15	24	25	44	45	64	65	84	85
5	124	25	28	45	76	65	112	85	129
6	35	26	27	46	133	66	91	86	87
7	25	27	65	47	65	67	85	87	91
8	9	28	45	48	49	68	69	88	91
9	28	29	35	49	66	69	85	89	99
10	33	30	49	50	51	70	169	90	91
11	15	31	49	51	65	71	105	91	115
12	65	32	33	52	85	72	85	92	93
13	21	33	85	53	65	73	111	93	301
14	15	34	35	54	55	74	75	94	95
15	341	35	51	55	63	75	91	95	141
16	51	36	91	56	57	76	77	96	133
17	45	37	45	57	65	77	247	97	105
18	25	38	39	58	133	78	341	98	99
19	45	39	95	59	87	79	91	99	145
20	21	40	91	60	341	80	81	100	153
21	55	41	105	61	91	81	85

Source: Wolfram MathWorld.

Congruence.

Introduction.

Prime Numbers have uses in Cryptography, important part of Computer Sciences.

Functional Paradigm uses Mathematics for Computing extensively, therefore this article.


Congruence.

If two numbers b and c have the property that their difference b-c is integrally divisible by a number m (i.e., (b-c)/m is an integer), then b and c are said to be 'congruent modulo m.' The number m is called the modulus, and the statement 'b is congruent to c (modulo m)' is written mathematically as:





If b-c is not integrally divisible by m, then it is said that 'b is not congruent to c (modulo m),' which is written:



The explicit '(mod m)' is sometimes omitted when the modulus m is understood by context, so in such cases, care must be taken not to confuse the symbol ≡ with the equivalence sign.

The quantity b is sometimes called the 'base,' and the quantity c is called the residue or remainder. There are several types of residues. The common residue defined to be nonnegative and smaller than m, while the minimal residue is c or c-m, whichever is smaller in absolute value.



Congruence arithmetic is perhaps most familiar as a generalization of the arithmetic of the clock. Since there are 60 minutes in an hour, 'minute arithmetic' uses a modulus of m=60. If one starts at 40 minutes past the hour and then waits another 35 minutes, 40+35≡15 (mod 60), so the current time would be 15 minutes past the (next) hour.



Similarly, 'hour arithmetic' on a 12-hour clock uses a modulus of m=12, so 10 o'clock (a.m.) plus five hours gives 10+5≡3 (mod 12), or 3 o'clock (p.m.)

Congruences satisfy a number of important properties, and are extremely useful in many areas of number theory. Using congruences, simple divisibility tests to check whether a given number is divisible by another number can sometimes be derived. For example, if the sum of a number's digits is divisible by 3 (9), then the original number is divisible by 3 (9).

Congruences also have their limitations. For example, if a≡b and c≡d (mod n), then it follows that a^x≡b^x, but usually not that x^c≡x^d or a^c≡b^d. In addition, by 'rolling over,' congruences discard absolute information. For example, knowing the number of minutes past the hour is useful, but knowing the hour the minutes are past is often more useful still.

Let a≡a^' (mod m) and b≡b^' (mod m), then important properties of congruences include the following, where => means 'implies':

1. Equivalence: a≡b (mod 0)=>a≡b (which can be regarded as a definition).

2. Determination: either or .

3. Reflexivity: a≡a (mod m).

4. Symmetry: a≡b (mod m) => b≡a (mod m).

5. Transitivity: a≡b (mod m) and b≡c (mod m) => a≡c (mod m).

6. a+b≡a^'+b^' (mod m).

7. a-b≡a^'-b^' (mod m).

8. ab≡a^'b^' (mod m).

9. a≡b (mod m) => ka≡kb (mod m).

10. a≡b (mod m) => aⁿ≡bⁿ (mod m).

11. a≡b (mod m₁) and a≡b (mod m₂) => a ≡b (mod [m₁,m₂]), where [m₁,m₂] is the least common multiple.

12. , where (k,m) is the greatest common divisor.

13. If a≡b (mod m), then P(a)≡P(b) (mod m), for P(x) a polynomial.

Properties (6-8) can be proved simply by defining:

a=a^'+rm
b=b^'+sm,

where r and s are integers. Then:

a+b=a^'+b^'+(r+s)m
a-b=a^'-b^'+(r-s)m
ab=a^'b^'+(a^'s+b^'r+rsm)m,

so the properties are true.

Congruences also apply to fractions. For example, note that:

2×4≡1 3×3≡2 6×6≡1 (mod 7),

so:

1/2≡4 1/4≡2 2/3≡3 1/6≡6 (mod 7).

To find p/q (mod m) where (q,m)=1 (i.e., q and m are relatively prime), use an algorithm similar to the greedy algorithm. Let q₀≡q and find:



where is the ceiling function, then compute:

q₁≡q₀p₀ (mod m).

Iterate until q_n=1, then:



This method always works for m prime, and sometimes even for m composite. However, for a composite m, the method can fail by reaching 0 (Conway and Guy 1996).

Finding a fractional congruence is equivalent to solving a corresponding linear congruence equation:

ax≡b (mod m).

A fractional congruence of a unit fraction is known as a modular inverse.

Source: Wolfram MathWorld.

Prime Numbers.

Prime Number.

A 'Prime Number' is a natural number greater than 1 that has no proper divisors other than 1 and itself.

The Natural Numbers are 0, 1, 2, 3, 4, ....

The list of prime numbers starts with 2, 3, 5, 7, 11, 13, .... Except for 2, all of these are odd, of course.



Haskell Implementation for Prime Number Test.

1. Let's define divides function.

It should check if number m divides n, and this is true when and only when remainder of dividing n by m equals 0. The definition of divides function can therefore be phrased in terms of a predefined function rem for finding the remainder of a division process:


divides m n = ((rem n m) == 0)

in Haskell, symbol '=' is used for "is defined as" and symbol '==' for identity relation (and operator). Single apostrophes are used in this phrase only for showing terminal symbols boundaries. Terminal symbol is single "word" in "programming language", from which no other "words" can be produced, so it's not a "definition" or "production". For more details, please read Literature about languages and compilers.

A line of Haskell code of the form: foo t = .... (or: foo t1 t2 = .... , or: foo t1 t2 t3 = .... , and so on) is called a Haskell equation. In such an equation, foo is called the function and t its formal argument (or: t1 t2 t3 its formal arguments).

Thus, in the Haskell equation: divides m n = ((rem n m) == 0) , divides is the function, m is the first formal argument, and n is the second formal argument.


2. Let's test 'divides' function.

We can put definition of divides in a file: 'prime.hs'. After that we can start Haskell Interpreter and load that file in memory.

Prelude> :l prime

Then we can call it, to execute as follows:

*Main>divides 5 7

or

*Main>divides 5 30

When executed, it will be parsed, or converted into processor instructions and will return results 'immediately', without prior compilation needed. Because it's interpreted by Interpreter, instead of being compiled by Compiler.




3. Let's define & test 'ld' function.

'ld' stands for 'least divisor'.

For convenience we can define supporting function 'ldf' that finds least divisor (pl: 'dzielnik') of a dividend (pl: 'dzielna') n, starting from a given threshold (pl: 'próg') k, with k ≤ n.

This means we are to find least divisor of n, which is not less than k.


We have:


ld n = ldf 2 n

ldf k n | divides k n = k
          | k^2 > n = n
          | otherwise = ldf (k+1) n





(TODO: explain, nicely and precisely, what happens in above example, and how we can think about guarded equations, such as with 'ldf' function.)

(TODO: finish Haskell Implementation for Prime Number Test).

(Source: [1]).