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

[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$.

 

[andrewkirk]

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.

 

[fishturtle1]

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?

 

[andrewkirk]

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$.

 

[fishturtle1]

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?