Sunday, February 6, 2011

Janos Bolyai and Fermat's Little Theorem


First, we solve the problem from last time:

One can also ascertain in advance which n-gons are “constructible” using only rule and straight edge, and which are not. It turns out such regular polygons are only possible provided the extension field has degree of 2. (I.e. the regular n-gon is only constructible if (Z + 1/Z) = 2 cos(2π/n).

Problem:

Prove this is the case, if the Z roots are determined by: cos(2π/n) + isin(2π/n), and the 1/Z roots are determined by: cos(2π/n) - isin(2π/n).

Solution:

The Z roots are determined by: cos(2π/n) + isin(2π/n), and

The 1/Z roots are determined by: cos(2π/n) - isin(2π/n).

Let: Z = cos(2π/n) + isin(2π/n) and

1/Z = cos(2π/n) - isin(2π/n)

Then:

[cos(2π/n) + isin(2π/n)] [cos(2π/n) - isin(2π/n)]

= cos2(2π/n) + sin2(2π/n)] = 1

(and recall by trig identity:

cos2(theta) + sin2(theta) = 1

Thus: (Z) (1/Z ) = 1

The preceding shows the angle is constructible, and the regular n-gon is only if the former holds.

And also:

(Z) + (1/Z) = (cos(2π/n) + isin(2π/n) ) + cos(2π/n) - isin(2π/n)

= 2 cos(2π/n)

Now on to Janos Bolyai!

Janos Bolyai is generally known for his contribution to non-Euclidean geometry and specifically the Bolyai-Lobachevsky geometry shown in the accompanying graphic. This geometry is held to correlate with a negatively curved (k= -1) space-time in general relativity (in contrast to the positive (k= +1) curvature of the sphere, attributed to Berhard Riemann).

Less well known are Boyai’s contributions to other areas of higher math, especially theorems to do with prime numbers. One of the most important of which is Fermat’s Little Theorem, and its inverse.

Fermat’s Little Theorem states that if p is a prime number and a is an integer not divisible by either p or q then the difference a^(p-1) – 1 is divisible by p, which is also written:
a^p-1 = 1(mod p)

The inverse of the above is that if a^p-1 = 1(mod p) holds, it does not necessarily follow that p is a prime.

Bolyai attempted to prove this inverse theorem but after a number of attempts, he gave up, concluding it was impossible and so the inverse of Fermat’s Little Theorem doesn’t hold in general. Though he didn’t find a general prime formula he did discover the first pseudo-prime.
Later, Bolyai examined under what conditions the congruence:

a^pq-1 = 1 (mod pq)

is satisfied, where p and q are primes and a is an integer divisible by neither p or q. Bolyai reasoned that (according to Fermat’s Little Theorem):

a^p-1 = 1 (mod p) and a^q-1 = 1 (mod q)

Then if one raised both sides of the first congruence to the power of (q-1) and both sides of the second congruence to the power (p-1), one would obtain:

a^(p-1)(q-1)= 1 (mod p) and

a^(p-1)(q-1) = 1(mod q)

a^(p-1)(q-1) = 1(mod pq)

Bolyai then observed that if the congruence:

a^(p+q-2) = 1 mod(pq) = a^(p-1)* a^(q-1) = mod(pq)

is true, then multiplying the two earlier expressions one arrives at the desired congruence:

a^pq-1 = 1 mod(pq)

Not content with this basic step, Bolyai set out to obtain the conditions which assure the validity of the preceding. Since: a^p-1 = 1 (mod p) and a^q-1 = 1 (mod q) then there must exist integers h and k such that: a^p-1 = 1 + hp, and a^q-1 = 1 + kq. Thus, the condition for the validity of the congruence is:

hp + hq = (a^p-1 – 1) + (a^q-1 – 1) = 0 (mod pq)

The above form is satisfied if p is a divisor of k and q is a divisor of h. According to Bolyai, this meant :

a^pq-1 = 1(mod pq)

is true of primes p and q for which: [a^p-1 – 1]/ pq and [a^q-1 -1]/pq are integers, in which case:

(a^p-1 -1)/q and (a^q-1 -1)/p are also integers.

Problem:

for the simple case for which a = 2, substitute primes p and q to obtain integers that satisfy the condition for congruence.

No comments: