Re: [FWP] Counting bits from the other end

[Jérôme Plût <Jerome.Plut@ens.fr> (by way of owner-fwp@technofile.org)]

>From fwp-l Sun Jun 24 16:22:41 2001

by way of owner-fwp@technofile.org a ÈcritÝ:
> Is it true that for an n bit number, the next highest prime number after n,
>is
> what should be used in this algorithm ? We tried it for 64-bit numbers

I recall your conjecture: given an integer n, the smallest integer m
such that
(*)  2^0,...,2^{n-1} are all distinct modulo m
is the smallest prime number p following m.

This conjecture is false: indeed, for n=5, we should have m=7; but
2^3 = 8 = 1 (mod. 7).

First remark: m must be odd. For if m=2k is even, we have
	(Z/mZ) = (Z/2) x (Z/k)
and k < n also satisfies (*).

Let's assume now that m is smaller than 2n (this is true according to
a theorem of Cebycev when m=p), and let e be the order of 2 modulo m
(that is, e is the smallest integer such that 2^e = 1 mod. m). Then e
divides the Euler function \phi(m); consequently, either e=\phi(m), or
e is smaller than m/2, and therefore e < n. Now note that (*) holds if
and only if e >= n. It follows that e = \phi(m), which means that 2 is
a generator of the multiplicative group of Z/mZ.

Finally: under the assumption that m <= 2n, m is the smallest
integer such that 2 is a generator of the multiplicative group of
Z/mZ.

-- 
	Jerome

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe