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 Z

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".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 Z

_{n}
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)~~

So far I've only encountered 2 mod n to have a finite order, which is either of the form 2rs, or rs

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).~~

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).

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

2

^{33968592}= 1 mod 407673751and 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