11.1.15

Life of Phi 2

In Mathematics a single counter-example is detrimental to even the most promising conjecture.

Such was the case, I thought, with Conjecture 2 from Finding Phi where I boldly predicted that the order of 2 mod n where n is the product of 2 distinct primes both greater than 2 was φ(n)/2.

I found a single counter-example: in one instance for n, φ(n)/4 was the smallest integer such that

2φ(n)/4 = 1 mod n

In that instance φ(n)/4 was the order of 2 mod n, which contradicted my conjecture that only φ(n)/2 could be the order of 2 mod n where n = p * q and p & q are two distinct primes both greater than 2. In other words, I thought φ(n)/2 was the smallest integer for which this equation 2φ(n)/2 = 1 mod n is true but it turns out that in some instances 2 has a smaller exponent that divides φ(n)/2.



However, I failed to record p and q so I technically can't reproduce this counter-example anymore.

In Types of Exponents it was established that there are several different types of smallest exponents, or finite orders of integers relatively prime to n in the cyclic group Zn 


Namely, if n = p * q where p, q are two distinct primes both greater than 2 and (p-1) = 2r and (q-1) = 2s for some positive integers r and s, then the possible orders are φ(n)/2 = (4rs)/2 = 2rs, φ(n)/4 = (4rs)/4 = rs, r, s, 2r, 2s, or 2.

So far I've only encountered 2 mod n to have a finite order, which is either of the form 2rs, or rs(although I'm currently unable to reproduce the last one)

The order of 2 mod n where n is the product of two distinct primes p and q both greater than 2 can not be equal to 2 since n is always greater than 4.

So theoretically, until proven otherwise, the order of 2 mod n can be either of the form 2rs, or rs, or 2r, or 2s, or r, or s for some positive r and s where r and s divide φ(n).

In my computational travels I have not been able to find a smaller order of 2 than 2rs (which is φ(n)/2) and maybe rs (which is φ(n)/4).

Here is the algorithm from Life of Phi 1, no nudges in the ribs required, but it does take more than 10 minutes of "Working..." to compute n that's 12 digits long, which is still better than "Invalid Input".





Update: I found a counter-example to Conjecture 2 in its current form, other than the obvious one above where n = 4699.

Example 1: Given n = p*q = 40609*10039 = 407673751

The result returned by my algorithm when 407673751 is plugged is 33968592, which means that


233968592 = 1 mod 407673751


and 33968592 is the smallest integer, for which the above statement is true

φ(n) = (p-1)*(q-1) = (40609-1)*(10039-1) = 407623104

and 407623104 divided by 33968592 = 12

I discovered many more examples out there, which leads to the following theorem

Conjecture 3: The order of 2 mod n where n is the product of two odd primes can be either of the form 2rs, or rs, or 2r, or 2s, or r, or s for some positive integers r and s where r and s divide φ(n).

But there is something even more interesting, and perhaps the reason why I did previously only see the order of 2 mod n to be of the form φ(n)/2: because I was only looking at primes p and q such that (p - 1) and (q - 1) have large prime factors.

The Fundamental Theorem of Arithmetic states that every integer except 0 can be represented as the product of primes and this prime factorization is unique up to reordering.

In Example 1 above (p - 1) and (q - 1) have relatively small prime factors. In particular,

p - 1 = 40609 - 1 =  40608 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 3 * 47
q - 1 = 10039 - 1 =  10038 = 2 * 3 * 7 * 239