Register to reply

Congruence Solving

by Bhatia
Tags: congruence, solving
Share this thread:
Bhatia
#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
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
micromass
#2
Jun8-11, 12:36 PM
Mentor
micromass's Avatar
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?)
Bhatia
#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
#4
Jun8-11, 01:26 PM
Mentor
micromass's Avatar
P: 18,331
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
#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
#6
Jun8-11, 04:01 PM
P: 218
9 is not prime.
Bhatia
#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