Euler’s Totient Theorem

Standard

Now I will present a wonderful fact about the coprimes to n — they form a group under multiplication mod n, which leads to:

If GCD(a,n) = 1 then aφ(n) = 1 (mod n).

Proof: take a to be any positive integer coprime to n.
Let A be the set of numbers coprime to n: A = {a1, a2, a3, …, aφ(n)}
Let aA be the product of the number, a, with each of the elements of A: aA = {aa1, aa2, aa3, …, aaφ(n)}
No two elements of aA are congruent mod n (see lemma 1, below*), so their residues mod n must be {a1, a2, a3, …, aφ(n)} in some order.
By equating the product of the numbers in set aA with the product of those in set A, mod n,
aφ(n)a1a2a3…aφ(n) = a1a2a3…aφ(n) (mod n)
Since a1a2a3…aφ(n) is coprime to n, we can divide both sides by a1a2a3…aφ(n), mod n, proving Euler’s Totient Theorem.

* Lemma 1: Why are no two elements of aA = {aa1, aa2, aa3, …, aaφ(n)} congruent, mod n?
Suppose a is a number coprime to n, and b and c are two different numbers, also coprime to n, in the range [1,n-1] and ab=ac, mod n.
Then ab-ac=nk, where k is an integer.
a(b-c)=nk, and since b-c is smaller than n in absolute value, a must be larger than k in absolute value.
a and n have no factors in common, so a|k, but a can’t divide k, since a is larger than k, a contradiction.


Other Totient Theorems

Let’s write m = 2n-1 for convenience.
Now 2n = m+1, so 2n = 1 (mod m), but no smaller (but still positive) power of 2 is equivalent to 1 (mod m).
So (2n)k = 1 (mod m), which means 2kn = 1 (mod m) for any integer, k.
2φ(m) = 1 (mod m), by Euler’s Totient Theorem.
We can divide φ(m) by n giving quotient q and remainder r such that φ(m) = qn+r, and so
2φ(m) = 2qn+r = 2qn 2r = 1 (mod m), and we know 2qn = 1 (mod m), so 2r = 1 (mod m), and 0 ≤ r < n, so r=0

Advertisements

Project Euler Problem No.5

Standard

Consider the numbers you have to test:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Break up the composite numbers to prime factors:
1, 2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5,
11, 2*2*3, 13, 2*7, 3*5, 2*2*2*2, 17, 2*3*3, 19, 2*2*5

For a number to be divisible by each of these groups, they have to show up among the prime factorization of our number.

The smallest number divisible by 1, 2, and 3 is 1*2*3 = 6.
To find the smallest number divisible by 1, 2, 3 and 4, we don’t have to multiply all of them together because there’s some redundancies. (2,2,3) is the smallest set that includes the sets (2), (3) and (2,2). So 2*2*3 = 12 is the smallest number divisible by 2, 3 and 4.

There are no 5s in the set (2,2,3), so the first number divisible by 1 through 5 has to be (2,2,3,5) = 60.

6 is 2*3, and we already have that, so we’ve found the number divisible by 1 through 6. Since 7 is prime, our new number has to be (2,2,3,5,7) = 420 in order to be divisible by everything up through 7.

8 is 2*2*2, so in order for (2,2,2) to be a subset we need to add one more two to get (2,2,2,3,5,7).

Continue on like this to get (2,2,2,3,3,5,7) for 9, which is already set for 10=2*5. 11 is prime, so we have (2,2,2,3,3,5,7,11). We’re all set for 12, because 12=2*2*3 and we have two 2s and a 3. For 13 we need (2, 2, 2, 3, 3, 5, 7, 11, 13). This already includes the factors of 14=2*7 and 15=3*5. For 16 we need an extra 2, to get (2, 2, 2, 2, 3, 3, 5, 7, 11, 13).

Then to 17: (2, 2, 2, 2, 3, 3, 5, 7, 11, 13). 18 is all set. 19 makes it (2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 19). And 20 is all set because we already have (2,2,5).

So the shortest number is
2*2*2*2 * 3*3 * 5*7*11*13*19 = 1,3693,680

Fermat number

Standard

Pierre de Fermat wrote to Marin Mersenne on December 25, 1640 that:
If I can determine the basic reason why
3, 5, 17, 257, 65 537, …,
are prime numbers, I feel that I would find very interesting results, for I have already found marvelous things [along these lines] which I will tell you about later. [Archibald1914].
This is usually taken to be the conjecture that every number of the form is prime. So we call these the Fermat numbers, and when a number of this form is prime, we call it a Fermat prime.
The only known Fermat primes are the first five Fermat numbers: F0=3, F1=5, F2=17, F3=257, and F4=65537. A simple heuristic shows that it is likely that these are the only Fermat primes (though many folks like Eisentsein thought otherwise).

In 1732 Euler discovered 641 divides F5. It only takes two trial divisions to find this factor because Euler showed that every divisor of a Fermat number Fn with n greater than 2 has the form k.2n+2+1. In the case of F5 this is 128k+1, so we would try 257 and 641 (129, 385, and 513 are not prime). Now we know that all of the Fermat numbers are composite for the other n less than 31. The quickest way to check a Fermat number for primality (if trial division fails to find a small factor) is to use Pepin’s test.

Gauss proved that a regular polygon of n sides can be inscribed in a circle with Euclidean methods (e.g., by straightedge and compass) if and only if n is a power of two times a product of distinct Fermat primes.

The Fermat numbers are pairwise relatively prime, as can be seen in the following identity:

F0F1F2…..Fn-1 +2 = Fn.
(This gives a simple proof that there are infinitely many primes.)
The quickest way to find out if a Fermat number is prime, is to use Pepin’s test [Pepin77]. It is not yet known if there are infinitely many Fermat primes, but it seems likely that there are not.