7.3.15

One Last Byte

I have been communicating with several comp sci research professors around the world regarding my Finding Phi Faster  algorithm and some of them were quick to scoff without reading while others promised to take the time to plough through the 50 pages of stuff I wrote here.  Fun times.

One comp sci professor who only read the brief email I sent him attacked my claim, upon which my Finding Phi Faster algorithm is based, without reading the proof for it. He basically claimed that phi(n)/2 is not a universal exponent when n is the product of two distinct odd primes without providing a counter example.

So I emailed my claim along with my proof, which uses results from Number Theory, to a prominent Group Theory researcher. I only emailed my claim with the proof as he is one of these great pure Mathematics researchers who like Mathematics for Mathematics' sake. Many Pure Mathematicians find Applied Mathematics insulting. After a week I got a response from him. He said that my logic is correct but my notation is confusing. He translated my claim into Group theoretic notation using results from advanced Group Theory:


$\phi(n)$ (two dollars mean that inside dollars  a math. symbol is typed)is equal to the number of all integers between $1$ and $n$
coprime with n. This number is precisely the order of the
group of units of the ring $Z/n$.

Facts:
1) if $n=m \cdot l $ (\cdot means central dot, i.e. the product) and integers
$m$ and $l$ are coprime then $\phi(n)=\phi(m) \cdot \phi(l)$.
2) if n=p$ is prime then $\phi(p)=p-1$ and the group of
units of $Z/p$ is cyclic
3) if $n=p \cdot q$ where $p$ and $q$ are different primes then
    $\phi(n)=(p-1) \cdot (q-1)$
4) Let $Z/n^*$ denotes the group of units of the ring $Z/n$. Let $n=p \cdot q$
as above. Then $Z/n^*$ is isomorphic to the direct product $Z/p^*$ and $Z/q^*$.
I will denote the direct product by $Z/p^* x Z/q^*$.

Altogether, your question can be restated as follows: is it true that any element of the ring $Z/P^* x Z/q^*$ has order dividing $\phi(n)/2=(p-1)(q-1)/2$?
The asnwer is ``Yes". Here is an argument. Let $a$ be a generator of the cyclic group
$Z/p^*$ and $b$ be the generator of $Z/q^*$. From the above facts we know that the order of $a$ is $p-1$ and the order of $b$ is $q-1$. Any element of the ring $Z/p^* x  Z/q^*$ is presented by a pair $(a^i,b^j)$. Note that $p-1$ and $q-1$ are even integers, hence $a^i$ taken to the power $(p-1)(q-1)/2$ gives $(a^(p-1))^(i(q-1)/2)=1$ and similarly for $b^j$. Therefore the element $(a^i,b^j)$ taken to the power $(p-1)(q-1)/2$ gives $(1,1)$. This is the end of the proof. 



Below is my claim and my proof, which uses results and definitions from Number Theory and tries to glue them together with results from Group Theory in a medley of fun:

Definition: If r and n are relatively prime (co-prime) integers with n > 0 and if the order of r mod n is equal to φ(n) then r is called a primitive root modulo n. [Page 336 from Elementary Number Theory, by Kenneth H. Rosen.]

Theorem: A positive integer n has a primitive root if and only if it is of the form pt, or 2p where p is an odd prime and t is a positive integer in Z.

Proof:  See pages 351 to 353 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 9.15 from chapter 9.3: The Existence of Primitive Roots

Claim: The order of any element co-prime with n in the group Zn under multiplication when n is the product of two distinct odd primes p and q , divides φ(n)/2

Proof:  Suppose that φ(n) is the smallest integer such that

aφ(n) = 1 mod n 

for any a relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2

The order of the group composed of all integers co-prime with n when n is the product of two distinct primes greater than 2 is φ(n) and for every element a relatively prime to n if has order k, then by Lagrange's Theorem the order of a divides the order of the group composed of all integers co-prime with n, namely k divides φ(n). Since it was assumed that φ(n) is the smallest integer such that  aφ(n) = 1 mod n  then k must be equal to φ(n).

However since n=p*q for some primes p and q both both greater than 2, then n does not have any primitive roots.  [See pages 351 to 353 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 9.15 from chapter 9.3: The Existence of Primitive Roots]


In other words, the group composed of all integers co-prime with n does not have any elements a relatively prime to n, whose order equals φ(n).Therefore, φ(n) is not the smallest integer such that  aφ(n) = 1 for any a relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2.

Therefore, the maximum order that an element of the group composed of all integers co-prime with n  can have is φ(n)/2  since 2 is the smallest integer > 1 to divide φ(n), which by is an even integer since both (p-1) and (q-1) are even.'.