Re: group theory question

On 29/09/2024 23:02, Peter Fairbrother wrote:

On 28/09/2024 04:48, Mike Terry wrote:

On 28/09/2024 01:53, Peter Fairbrother wrote:

 

Note: most posters here don't go for top-posting, preferring responses intermixed with the original quoted text.  Just saying, because some people will get cross with top posters!

 I shall beat myself up immediately.
 [...]
 

Is the set e^2^n mod p (where e is a generator and element of the multiplicative group mod p, p is prime and n=0 to p) equal to the set of quadratic residues of the group?

>
No - you could just try out a couple of low p examples to see it doesn't work.  E.g. p=7.
>
generators:     3 and 5
qres:           1,2,4
>
e:              3       5
               ---     ---
e^(2^0)         3       5
e^(2^1)         2       4
e^(2^2)         4       2
e^(2^3)         2       4
e^(2^4)         4       2
...
>
both are missing qr: 1

 Ok, thanks for the help - I should have asked:
 Is the set S = g^(2^n) mod p (where g is any generator / element of the multiplicative group mod p, p is prime and n=1 to p) plus the element 1 equal to the set QR of quadratic residues of the aforementioned group?
 

(Note we can calculate g^(2^n) = g^(2*2^(n-1)) = g^(2^(n-1))^2 iteratively by squaring, taking mod p after each iteration.

 Yes, so we would never get a non-QR in S.

correct (given you're not considering n=0)

But do we get all the QRs?

I'm not sure what your question is. It sounds like you're asking whether for all [odd?] p and all choice of generators g, the set S(p,g) U {1} = QR(p) ?  I.e. do the conditions you describe imply the conclusion that S(p) U {1} = {quadratic residues mod p}?
If so, what small p have you tried so far, and what was the result?

 A proof?

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