Congruence Solving


by Bhatia
Tags: congruence, solving
Bhatia
Bhatia is offline
#1
Jun8-11, 12:22 PM
P: 11
Let p be a prime number and d / p-1 .

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.
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
micromass
micromass is online now
#2
Jun8-11, 12:36 PM
Mentor
micromass's Avatar
P: 16,701
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?)
Bhatia
Bhatia is offline
#3
Jun8-11, 01:05 PM
P: 11
Quote Quote by micromass View Post
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?)
Thanks for your reply

Going by your idea

Let p= 5, then since d / p-1 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.

micromass
micromass is online now
#4
Jun8-11, 01:26 PM
Mentor
micromass's Avatar
P: 16,701

Congruence Solving


Quote Quote by Bhatia View Post
Thanks for your reply

Going by your idea

Let p= 5, then since d / p-1 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 .....
You're working (mod 5) here, so I suggest that you express the x also in (mod 5). (thus x can be 0,1,2,3 or 4).
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).

So I am thinking atleast d....
This is certainly correct, but the above example suggest exactly d!

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{p-1}{d}}[/tex]


By the way, do you know some group theory? It would make it a lot easier...
Bhatia
Bhatia is offline
#5
Jun8-11, 03:58 PM
P: 11
Quote Quote by micromass View Post
You're working (mod 5) here, so I suggest that you express the x also in (mod 5). (thus x can be 0,1,2,3 or 4).
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).

This is certainly correct, but the above example suggest exactly d!

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{p-1}{d}}[/tex]


By the way, do you know some group theory? It would make it a lot easier...
Thank you so much...

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 ^ (p-1)/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 !
Yuqing
Yuqing is offline
#6
Jun8-11, 04:01 PM
P: 218
9 is not prime.
Bhatia
Bhatia is offline
#7
Jun8-11, 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