--- In

primenumbers@yahoogroups.com,

"rach" <maths_forall@...> wrote:

> this conjecture

The proof that your method works is very easy.

For odd n > 1, the k-th term in your sequence is congruent to

2^(1-k) - 1 modulo n, as is easily proven by induction.

Thus the first term that is congruent to 1 modulo n occurs

when k is the order of 2 modulo n.

Example, with n = 23:

print(vector(11,k,2^(1-k)-1)%23);

[0, 11, 5, 2, 12, 17, 8, 15, 7, 3, 1]

So there is no "conjecture": just a trivial proof that you

find the correct order by performing a total number of

divisions by 2 that is one less than the order.

As I remarked, Pari-GP is 500000 times faster in the case of

n = 8988229, because it exploits the fact that znorder(Mod(2,n))

is a divisor of eulerphi(n). In this case, n is prime and

hence the order is a divisor of

eulerphi(n) = n - 1 = 2^2*3^2*61*4093.

To prove that the order is in fact n - 1, in this case,

we need to prove that 2^((n-1)/d) is not congruent to 1 modulo n

for any of the prime divisors d = 2, 3, 61, 4093 of eulerphi(n).

We do may do this by binary modular exponentiation:

n=8988229;

for(j=1,4,d=[2,3,61,4093][j];if(Mod(2,n)^((n-1)/d)==1,print(fail)));

[no failures]

This took 8 microseconds. Your method took 8 seconds.

David