# Congruence: Solving Let p be a Prime Number

• Bhatia
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.
Bhatia
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.

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?)

micromass said:
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?)

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.

Bhatia said:

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

$$a^{\frac{p-1}{d}}$$By the way, do you know some group theory? It would make it a lot easier...

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

$$a^{\frac{p-1}{d}}$$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.

Last edited:
9 is not prime.

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.

Replies
17
Views
1K
Replies
2
Views
1K
Replies
1
Views
3K
Replies
2
Views
1K
Replies
1
Views
1K
Replies
19
Views
1K
Replies
11
Views
1K
Replies
2
Views
1K
Replies
8
Views
1K
Replies
16
Views
2K