Register to reply 
Congruence Solving 
Share this thread: 
#1
Jun811, 12:22 PM

P: 11

Let p be a prime number and d / p1 .
Then which of the following statements about the congruence? x ^d = 1( mod p) is / are correct : 1. It does not have a solution 2 atmost d incongurent solutions 3 exactly d incongruent solutions 4 aleast d incongruent solutions. 


#2
Jun811, 12:36 PM

Mentor
P: 18,331

Hi Bhatia!
What do you think? And why? (maybe try to work it out for a concrete example of p and d? Like p=11 and d=5?) 


#3
Jun811, 01:05 PM

P: 11

Going by your idea Let p= 5, then since d / p1 then I guess we have d= 1, 2, 4...then solving x^ d = 1 (mod 5) for d=1, x=1 for d=2, x= 4, 6,9,11,14, .... for d=4, x= 2, 3,4,6, 7 ..... So I am thinking atleast d.... But not sure....I did not study number theory at graduation level. 


#4
Jun811, 01:26 PM

Mentor
P: 18,331

Congruence Solving
When I do this, I get for d=1: x=1 for d=2: x=1,4 for d=4: x=1,2,3,4 Solutions like 9 are superfluous here, since 9=4 (mod 5). To prove this consider a number a coprime with p (for example take a=2 when p is odd). Then what can you say about [tex]a^{\frac{p1}{d}}[/tex] By the way, do you know some group theory? It would make it a lot easier... 


#5
Jun811, 03:58 PM

P: 11

I agree with this...I realized my mistake x should be strictly less than p. Taking p to be odd (as suggested) p= 5 , then d =1, 2, 3, 4. Does 2 ^ (p1)/d imply the following we get: for d=1, 2^ 4 = 16 works for d=1 that is , 16= 1 (mod 5). for d=2, 2 ^ 2= 4 works for d=2 that is, 4^2 = 1( mod 5) for d= 4, 2 ^ 1 =2 works for d =4, that is , 2^ 4 = 1 (mod 5). Does this mean that we can generate other values of x ( above we get x= 16)....so x has to be at least d but can be more than d as well. Please help ! 


#6
Jun811, 04:01 PM

P: 218

9 is not prime.



#7
Jun811, 04:04 PM

P: 11

Thanks, Yuqing.



Register to reply 
Related Discussions  
Solutions to na=0 (mod m)  Linear & Abstract Algebra  4  
Solving a linear congruence  Calculus & Beyond Homework  0  
Congruence  subject difficulty  General Math  0  
Solving a congruence  Calculus & Beyond Homework  2  
Congruence help  Linear & Abstract Algebra  5 