Congruence: Solving Let p be a Prime Number

  • Thread starter Bhatia
  • Start date
In summary, for a prime number p and d / p-1, the congruence x^d = 1 (mod p) has exactly d incongruent solutions, where x is a number coprime with p. This can be proven by considering a^((p-1)/d) for any number a coprime with p, which always results in a solution. Group theory can be used to make this proof easier.
  • #1
Bhatia
11
0
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.
 
Physics news on Phys.org
  • #2
Hi Bhatia! :smile:

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
micromass said:
Hi Bhatia! :smile:

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 :smile:

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.
 
  • #4
Bhatia said:
Thanks for your reply :smile:

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...
 
  • #5
micromass said:
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 !
 
Last edited:
  • #6
9 is not prime.
 
  • #7
Thanks, Yuqing.
 

1. What is the definition of congruence?

Congruence refers to the relationship between two numbers or geometric figures that are equal in size, shape, and measure.

2. How do you solve equations involving congruence?

To solve equations involving congruence, you can use the properties of congruence, such as the reflexive, symmetric, and transitive properties, to manipulate the equations and find the value of the unknown variable.

3. What is the significance of using "p" as a prime number in congruence equations?

In congruence equations, using "p" as a prime number allows for a more simplified and efficient way to solve the equations, as it eliminates the possibility of the equation having multiple solutions.

4. Can congruence be used in any type of equation?

No, congruence can only be used in equations involving geometric figures or numbers. It cannot be used in equations with variables that represent real-life quantities, such as distance or time.

5. How is congruence used in real-world applications?

Congruence is used in various fields, such as architecture, engineering, and art, to ensure that objects or structures are symmetrical and proportional. It is also used in cryptography to ensure the security of messages and data.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
842
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
761
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
290
  • Linear and Abstract Algebra
Replies
1
Views
730
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
3K
  • Linear and Abstract Algebra
Replies
8
Views
859
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
Replies
7
Views
782
Back
Top