Modular equation solution

[otutusaus]

I apologize if the question is trivial, I have math as a hobby.
Given a prime number p and the equation 2^x = 1 mod p, Fermat little theorem gives the solution x=p-1.
When does the equation have other solutions for x<p? And which are the other solutions?
Thanks.

[Mini-Geek]

Using the following PARI/GP commands:
f(p)=for(X=0,p-1,if(Mod(2^X,p)==Mod(1,p),print(X," ",p)))
forprime(p=2,101,f(p))
I made this list, where "x p" means 2^x = 1 mod p

0 2
0 3
2 3
0 5
4 5
0 7
3 7
6 7
0 11
10 11
0 13
12 13
0 17
8 17
16 17
0 19
18 19
0 23
11 23
22 23
0 29
28 29
0 31
5 31
10 31
15 31
20 31
25 31
30 31
0 37
36 37
0 41
20 41
40 41
0 43
14 43
28 43
42 43
0 47
23 47
46 47
0 53
52 53
0 59
58 59
0 61
60 61
0 67
66 67
0 71
35 71
70 71
0 73
9 73
18 73
27 73
36 73
45 73
54 73
63 73
72 73
0 79
39 79
78 79
0 83
82 83
0 89
11 89
22 89
33 89
44 89
55 89
66 89
77 89
88 89
0 97
48 97
96 97
0 101
100 101

Trivially, there is a solution at x=0, since 2^0 = 1. And since these are primes, we know that 2^(p-1) = 1 mod p. The other solutions seem to be related to the factors of p-1, but I'm not sure exactly how.

[science_man_88]

Originally Posted by Mini-Geek

Using the following PARI/GP commands:
f(p)=for(X=0,p-1,if(Mod(2^X,p)==Mod(1,p),print(X," ",p)))
forprime(p=2,101,f(p))
I made this list, where "x p" means 2^x = 1 mod p

0 2
0 3
2 3
0 5
4 5
0 7
3 7
6 7
0 11
10 11
0 13
12 13
0 17
8 17
16 17
0 19
18 19
0 23
11 23
22 23
0 29
28 29
0 31
5 31
10 31
15 31
20 31
25 31
30 31
0 37
36 37
0 41
20 41
40 41
0 43
14 43
28 43
42 43
0 47
23 47
46 47
0 53
52 53
0 59
58 59
0 61
60 61
0 67
66 67
0 71
35 71
70 71
0 73
9 73
18 73
27 73
36 73
45 73
54 73
63 73
72 73
0 79
39 79
78 79
0 83
82 83
0 89
11 89
22 89
33 89
44 89
55 89
66 89
77 89
88 89
0 97
48 97
96 97
0 101
100 101

Trivially, there is a solution at x=0, since 2^0 = 1. And since these are primes, we know that 2^(p-1) = 1 mod p. The other solutions seem to be related to the factors of p-1, but I'm not sure exactly how.

well one other major subset of those is ((p-1)/2) don't know about the others.

[otutusaus]

Thank you mini-geek.
Do you think there is any expression x=f(p) for the solutions others than the trivial and the Fermat's?

[axn]

Originally Posted by otutusaus

Thank you mini-geek.
Do you think there is any expression for the solutions others than the trivial and the Fermat's?

In PARI/GP you can do znorder(Mod(2,p))

[R.D. Silverman]

Originally Posted by otutusaus

I apologize if the question is trivial, I have math as a hobby.
Given a prime number p and the equation 2^x = 1 mod p, Fermat little theorem gives the solution x=p-1.
When does the equation have other solutions for x<p? And which are the other solutions?
Thanks.

May I suggest that you try to learn some number theory?
Consult any good elementary number theory book. I can
recommend several.

One could always try Google.

Hint: look up "Lagrange's Theorem"

[R.D. Silverman]

Originally Posted by otutusaus

Thank you mini-geek.
Do you think there is any expression x=f(p) for the solutions others than the trivial and the Fermat's?

He doesn't know the answer.

I will be happy to answer the question after you have
shown that you have done some reading.

Get back to us after you have taken my earlier suggestions
and I will be happy to answer any unanswered questions
AFTER you show us that you are willing to do some work.

[otutusaus]

Originally Posted by R.D. Silverman

He doesn't know the answer.

I will be happy to answer the question after you have
shown that you have done some reading.

Get back to us after you have taken my earlier suggestions
and I will be happy to answer any unanswered questions
AFTER you show us that you are willing to do some work.

I apologize, the answer was somewhere else I couldn't find before. I should have read about "multiplicative group modulo a prime" and "multiplicative order".
Thanks for the hint.

[R.D. Silverman]

Originally Posted by otutusaus

I apologize, the answer was somewhere else I couldn't find before. I should have read about "multiplicative group modulo a prime" and "multiplicative order".
Thanks for the hint.

Look up Lagrange's Theorem.

[R.D. Silverman]

Originally Posted by otutusaus

I apologize, the answer was somewhere else I couldn't find before. I should have read about "multiplicative group modulo a prime" and "multiplicative order".
Thanks for the hint.

No apology needed. You asked a reasonable question. But learning
the answer is going to require some reading on your part. If you
have something that you read but don't understand I will be
happy to help.

If you are unwilling to do the work, then please leave.

And your English is excellent.

The question you asked has been asked many times in the forum
and there has been extended discussion in the past. Perhaps
reading past posts from this forum might help.

[Raman]

2 should be a primitive root for p in this case.

2 is a quadratic residue (mod p), and hence its order is a divisor of (p-1)/2, thus not a primitive root whenever that p is congruent to 1 or 7 (mod 8).

But when does the order of 2 (mod p) be (p-1)/q, for other factors 'q' of p-1, such that q is not divisible by 2? For example, it is true that 2 is not a quadratic residue (mod 43), but not a primitive root as well. Its order is rather 14. Seems that I should do so with some reading upon this part.

An important question that I had encountered with recently: for what values of N, not necessarily prime, does there exist primitive roots (mod N), i.e. there exist with generators for that cyclic multiplicative group with N elements.
1, 2, 4, p^x, 2p^x. That's all, nothing more else. I saw that its proof rather digs deeper into that binomial theorem, that way, to be precise.