# Congruence and Primes: Proving the Order of an Integer Modulo a Prime

• fishturtle1
In summary, the order of b divides p - 1, and so b is either 1 or pk+1, where p is prime and k is an integer.
fishturtle1

## Homework Statement

1.31 Let ##p## be a prime and let ##q## be a prime that divides ##p - 1##.
a) Let ##a \epsilon F^*_p## and let ##b = a^{(p - 1)/q}##. Prove that either ##b = 1## or else ##b## has order ##q##. (Recall that order of ##b## is the smallest ##k \ge 1## such that ##b^k = 1## in ##F^*_p##. Hint. Use Proposition 1.30).

## Homework Equations

Proposition 1.30: Let ##p## be a prime and let ##a## be an integer not divisible by ##p##. Suppose that ##a^n \equiv 1 (\mod p)##. Then the order of ##a## modulo ##p## divides ##n##. In particular, the order of ##a## divides ##p - 1##.

## The Attempt at a Solution

Proof: Let ##a \epsilon F^*_p## and let ##b = a^{(p - 1)/q}##. Raising both sides to the qth power, we have ##b^q = a^{p - 1}##. Therefore, ##b^q \equiv a^{p - 1} (\mod p)##. Since ##a < p##, we can say ##p## does not divide ##a##. By Fermat's Little Theorem, we have ##a^{p - 1} \equiv 1 (\mod p)##. Since ##\equiv## is transitive, we have ##b^q \equiv 1 (\mod p)##. Thus, ##b = pk + 1##, where k is some integer. So ##b = 1## or ##b = pk + 1##, where ##p \neq 0##.

But I'm not sure how or if ##p \neq 0## implies ##q## is the order of ##b##.

You haven't used Proposition 1.30. Use it on the 3rd last sentence in your attempted proof and you're there. Note that you'll have to substitute some letters. The ##a## of the proposition is not the ##a## of the problem.

andrewkirk said:
You haven't used Proposition 1.30. Use it on the 3rd last sentence in your attempted proof and you're there. Note that you'll have to substitute some letters. The ##a## of the proposition is not the ##a## of the problem.
Thank you for the response

Proof: Let ##a \epsilon F^*_p## and let ##b = a^{(p - 1)/q}##. Raising both sides to the qth power, we have ##b^q = a^{p - 1}##. Therefore, ##b^q \equiv a^{p - 1} (\mod p)##. Since ##a < p##, we can say ##p## does not divide ##a##. By Fermat's Little Theorem, we have ##a^{p - 1} \equiv 1 (\mod p)##. Since ##\equiv## is transitive, we have ##b^q \equiv 1 (\mod p)##. Therefore ##p## does not divide ##b##. By Proposition 1.30, we have the order of ##b## divides ##p - 1##. We proceed by contradiction. Let ##x## be the order of ##b## and suppose ##x## is composite. Then ##x = mn## where ##m, n## are integers and ##m,n < x##. But that means the order of ##b## = min{m,n} ##\neq x##, a contradiction. Thus, the order of ##b## is some prime that divides ##p - 1##, that is the order of ##b## is ##q##.

We can conclude if ##a \epsilon F^*_p## and ##b = a^{(p - 1)/q}##, then ##b = 1## or ##b## has order ##q##. []i'm not sure if I have to prove/mention that q is the smallest prime number that divides p - 1. I believe this is true, but since we are only given q is some prime that divides p - 1, it could be that there exists a q' < q where q' is prime and q' divides p - 1. Then q' would be the order of b...Reading the statement again, it seems we just need to prove either b = 1 or b has an order that is prime. We've done that, but more specifically do we need to mention that q should be the smallest prime that divides p - 1?

That's way more complex than it needs to be.

At the start of your third line you conclude that ##b^q\equiv 1## mod ##p##.

The premise for Proposition 1.30 is ##a^n\equiv 1## mod ##p##. Make the appropriate substitutions to match this to the previous line, then state the conclusion of Prop 1.30 with the substituted terms.

At no point beyond your second line should you need to refer to ##p-1##.

andrewkirk said:
That's way more complex than it needs to be.

At the start of your third line you conclude that ##b^q\equiv 1## mod ##p##.

The premise for Proposition 1.30 is ##a^n\equiv 1## mod ##p##. Make the appropriate substitutions to match this to the previous line, then state the conclusion of Prop 1.30 with the substituted terms.

At no point beyond your second line should you need to refer to ##p-1##.

Proof: Let ##a \epsilon F^*_p## and let ##b = a^{(p - 1)/q}##. Raising both sides to the qth power, we have ##b^q = a^{p - 1}##. Therefore, ##b^q \equiv a^{p - 1} (\mod p)##. Since ##a < p##, we can say ##p## does not divide ##a##. By Fermat's Little Theorem, we have ##a^{p - 1} \equiv 1 (\mod p)##. Since ##\equiv## is transitive, we have ##b^q \equiv 1 (\mod p)##. P is prime, therefore ##p## does not divide ##b##. By Proposition 1.30, the order of ##b## modulo ##p## divides n. In particular, the order of ##b## divides ##p - 1##. So we can conclude that ##b = 1## or the order of ##b## modulo ##p## is ##q##. []I don't think this works but maybe I'm overthinking it. We're only told that ##q## is some prime number that divides ##p - 1##. So won't it be an assumption that it is the least prime number that divides ##p - 1##? And don't we need this assumption to be true to complete the proof?

## What is the definition of congruence?

Congruence is a mathematical concept that describes the relationship between two numbers or objects that have the same remainder when divided by a given number.

## What is the significance of congruence in mathematics?

Congruence is an important concept in mathematics as it helps in determining patterns and relationships between numbers and objects. It also plays a key role in many mathematical proofs and theorems.

## What are primes?

Primes are numbers that can only be divided by 1 and itself. They have exactly two factors, making them unique compared to other numbers.

## What is the connection between congruence and primes?

There is a special type of congruence called modular arithmetic, which is used to study the properties of prime numbers. In modular arithmetic, numbers are divided into classes based on their remainders when divided by a given number, and this helps in understanding the properties of primes.

## How are congruence and primes used in cryptography?

Congruence and primes are used in cryptography to create secure algorithms for encryption and decryption. The security of these algorithms relies on the difficulty of factoring large numbers, which is closely related to the properties of primes and congruence.

• Calculus and Beyond Homework Help
Replies
30
Views
2K
• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
9
Views
1K
• Calculus and Beyond Homework Help
Replies
13
Views
2K
• Calculus and Beyond Homework Help
Replies
16
Views
1K
• Calculus and Beyond Homework Help
Replies
16
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
18
Views
2K