Re: group theory question

On 09/10/2024 17:21, Phil Carmody wrote:

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

Well if the conjecture fails, a counter-example suffices.  But like I
said, I'm not sure what you're asking.  It should be apparent from
tests that some (p,g) values work and some do not.

 Mod(3,17) is a generator, but its 2^n-th powers hit Mod(1,17) really
quickly.
 Phil
 

Also p=13.  Well, the powers don't hit 1, but quickly cycle with a period of 2.  Cycling "too soon" is the general way different primes fail, rather than specifically hitting 1.
Here's a different (simpler if correct) way of looking at things:
[note I'm only considering odd primes p...]
If g is a generator, the quadratic residues [mod p] will be g^0=1, g^2, g^4, ...g^(p-1).  So the question is whether g^2, g^4, g^8, g^16, ... g^(2^(p-1)/2) enumerates the same set.
This will be the same regardless of the generator chosen, as it is more about the powers of 2 [mod p-1], rather than a QR question.  Note that by Fermat's Little Theorem, 2^(p-1) = 1 [mod p] which is why I reduce the exponents mod (p-1) rather than mod p which might be expected.
So it seems we want to know when 2 multiplicatively generates the even numbers [mod p-1].  Hmm, if we divide everything by 2, maybe that becomes simply "2 generates the whole of Z mod (p-1)/2" ??
I'm not 100% sure on all this, but makes me think that perhaps for someone working in this area (e.g. number theory) it would be easy for them to characterise which p work and give an explanation why... I expect this would be well known.   For me it is all too long ago - I was a student more than 40 years ago, and even then I didn't do much number theory (which I regret slightly).
Just by inspection (mucking about in an Excel spreadsheet) it seems most p won't work due to 2^n [mod p-1] quickly hitting a cycle, but a few p DO work, so there's an interesting question as to why.
Working p:  (2), 3, 5, 7, 11, 23, 59, ...
(Then again I might have mucked up the spreadsheet or just misrecorded something, so don't take that as gospel!)
Hmm, one more thing it reminds me of is expansions for fractions like 1/n.  For certain n these achieve a maximum length before repeating, whereas others do not.  Like 1/7 = 0.142857[repeat], and 6 is the maximum length before the division is forced to repeat because there are only 6 possible remainders at each step.  Don't know if this is really relevant, it just brings this to mind for me.
Regards,
Mike.