# Let $ord(a) = n$. Let $k$ be an integer such that every prime factor of $k$ is a factor of $n$. Prove: If $a = b^k$ then $ord(b) = nk$.

This is Pinter 10.H.6.

Let $$a$$ have order $$n$$.

Let $$k$$ be an integer such that every prime factor of $$k$$ is a factor of $$n$$.

Prove: If $$a$$ has a kth root $$b$$, then $$ord(b) = nk$$.

Pinter will often set things up so that previous results in an exercise set will be helpful in the following exercises. So, here's a result from 10.H.5:

If $$a$$ has order $$n$$ and $$a$$ has a kth root $$b$$ then $$b$$ has order $$nk/l$$, where $$n$$ and $$l$$ are relatively prime.

Here's what I have so far.

$$ord(a) = n \tag{1}$$

$$a = b^k \tag{2}$$

By (1):

$$a^n = e$$

Substitute (2):

$$(b^k)^n = e$$

$$b^{kn} = e$$

If $$kn$$ is the smallest number such that this is true, then $$ord(b) = kn$$.

Let's assume there is a number smaller than $$kn$$ such that $$b$$ raised to this power is equal to $$e$$.

We only need to consider factors of $$kn$$.

Let's let one of these numbers be $$p$$, a prime.

$$p | k$$

$$k = p k' \tag{4}$$

Let's assume:

$$b^p = e. \tag{3}$$

Eq (2):

$$a = b^k$$

Substitute (4):

$$a = b^{pk'}$$

$$a = (b^p)^{k'}$$

Substitute (3):

$$a = (e)^{k'}$$

$$a = e$$

This approach doesn't seem to help. :-)

Moreover, it doesn't use the fact that prime factors of $$k$$ are also factors of $$n$$.

What's a good approach to solving this problem?

Note: I'm primarily interested in solutions that only use what's available in Pinter's text up to this point and that solve the problem in the way that Pinter is likely expecting the reader to. Of course, feel free to post solutions that step outside of this constraint as they are often interesting.

It seems Pinter expects the reader to solve this based on how exercises 10.H.1, 10.H.2 and 10.H.3 were solved. He doesn't say this explicitly however we can't for sure assume this.

# Approach 2

This approach continues right after (3) is established above.

By (3):

$$b^p = e$$

Raise both sides to $$k$$:

$$(b^p)^k = (e)^k$$

$$(b^k)^p = e$$

Substitute (2):

$$(a)^p = e$$

We know that $$p$$ is a factor of $$k$$ and also a factor of $$n$$ so:

$$p < n$$

which violates (1).

I think I'd need to be a little more rigorous in showing that $$p < n$$.

# Bill's approach

Here's a step-by-step explanation of Bill's answer below.

We're given:

$$ord(a) = n \tag{1}$$

$$a = b^k \tag{2}$$

By (1):

$$a^n = e \tag{5}$$

Substitute (2):

$$(b^k)^n = e$$

$$b^{kn} = e \tag{6}$$

Eq (5):

$$a^n = e$$

Substitute (6):

$$a^n = b^{kn} \tag{7}$$

We'll be using the order test. I.e.:

$$ord(a) = n$$ iff $$a^n = e$$ but $$a^{n/p} ≠ e$$ for every prime $$p|n$$.

In other words, if $$a^n = e$$ and you can show that for every prime $$p|n$$ that $$a^{n/p} ≠ e$$ then $$ord(a) = n$$.

So for our case, if we can show that $$b^{kn/p} ≠ e$$ for each prime $$p|kn$$ then $$ord(b) = kn$$ by the order test.

The exercise mentions:

every prime factor of $$k$$ is a factor of $$n$$

Thus, if $$p|kn$$ then

$$p|n \text{ or } p|k \text{ (and thus p|n by the given statement)} \tag{8}$$

Eq (7):

$$a^n = b^{kn}$$

Divide both powers by $$p$$:

$$a^{n/p} = b^{kn/p}$$

We know that    n/p is an integer by (8).
We know that   kn/p is an integer by (8).


$$n/p < n$$ so $$a^{n/p} ≠ e$$ (Otherwise, (1) would be violated.)

So:

$$b^{kn/p} ≠ e$$

By order test:

$$ord(b) = kn$$

# ganeshie8's approach

Here's a step-by-step explanation of the answer provided by ganeshie8.

We'll be using 10.G.5:

Let $$a \in G$$. Let $$ord(a) = n$$. Then $$ord(a^m) = lcm(m,n)/m$$.

We're given the following:

$$ord(a) = n \tag{1}$$

$$a = b^k \tag{2}$$

$$k \text{ is an integer such that every prime factor of } k \text{ is a factor of }n \tag{3}$$

Let's begin. Let:

$$ord(b) = u \tag{7}$$

By 10.G.5:

$$ord(b^k) = lcm(k,u)/k$$

From basic number theory, $$gcd(k,u) lcm(k,u) = ku$$ thus $$lcm(k,u)/k = u/gcd(k,u)$$ so:

$$ord(b^k) = u/gcd(k,u)$$

Substitute (2):

$$ord(a) = u/gcd(k,u)$$

Substitute (1):

$$n = u/gcd(k,u) \tag{8}$$

$$n | u$$

Let:

$$u = na \tag{9}$$

Eq (8):

$$n = u/gcd(k,u)$$

Substitute (9):

$$n = na/gcd(k,na)$$

Divide by $$n$$:

$$1 = a/gcd(k,na)$$

$$gcd(k,na) = a$$

Divide by $$a$$:

$$gcd(k,na)/a = a/a$$

$$gcd(k/a,n) = 1$$

Thus $$k/a$$ and $$n$$ are relatively prime. By (3):

$$k/a = 1$$

$$k = a \tag{10}$$

Eq (9):

$$u = na$$

Substitute (10):

$$u = nk$$

Substitute (7):

$$ord(b) = nk$$

• Hint: show that the problem in the general case is implied by the particular case “k prime”. Aug 18, 2019 at 21:23
• Did neither answer help? Aug 20, 2019 at 1:31
• @BillDubuque Hey Bill! I've been tied up with a few things since I posted this. I'm going to make some time this week to sit down with the answers. Thanks for the answers and for following up! Aug 20, 2019 at 2:04
• Ok, please feel welcome to ask for elaboration if need be. Aug 20, 2019 at 2:07

Let $$ord(b) = u$$,

then $$ord(b^k) = \frac{u}{\gcd(u,k)} = n$$

$$\Rightarrow n\mid u$$, let $$u = na$$
$$\gcd(na,k) = a$$

This means $$\gcd(n,k/a)=1$$.
Since we're given that each prime factor of $$k$$ divides $$n$$ it follows $$k/a=1$$.
$$\Rightarrow a = k$$
$$\Rightarrow u = na = nk$$

• Thanks ganeshie8! Aug 23, 2019 at 10:53
• From basic number theory: $u/gcd(u,k) = lcd(u,k)/k$. So in the above, $ord(b^k) = u/gcd(u,k)$ can be converted to $ord(b^k) = lcd(u,k)/k$. This is the result from 10.G.5! So actually, this solution builds on a previous exercise in Pinter. This is likely the approach expected by Pinter. (Although, he usually points out previous exercises to use as hints and he didn't in this case.) Sep 3, 2019 at 17:13
• I knew Pinter must have covered it as I remember doing a similar exercise problem right after that theorem in Burton. I find the gcd version of that a bit less confusing to memorize though.. Sep 3, 2019 at 17:57
• I've updated the question to include a step-by-step explanation of your answer. Let me know if you see anything there that was not your intention. Thanks again ganeshie8! Sep 3, 2019 at 22:36

$$b^{\large kn}\! = a^{\large n} = 1\,$$ so, by the Order test, showing $$\,b^{\large kn/p}\neq 1$$ for each prime $$p\mid kn$$ implies $$\,{\rm ord}\, b = kn.\,$$ But by the hypothesis $$\,p\mid kn\,\Rightarrow\,p\mid n\,$$ thus $$\,b^{\large kn/p} = a^{\large n/p}\neq 1\,$$ by $$\,{\rm ord}\,a = n.\,$$ QED

• In case it's not clear: $\,\large p\mid kn\,\Rightarrow\, p\mid n\$ or $\ \large p\mid k\, (\Rightarrow p\mid n\,$ by hypothesis) $\ \$ Aug 18, 2019 at 22:19
• Thanks Bill! The order test seems quite useful. I'm not sure that the order test is covered in Pinter up to chapter 10. But this is still an interesting approach. Aug 23, 2019 at 10:49
• @dharmatech Even if it is not explicitly stated or named, you already have all the ingredients needed to complete the simple proof of the Order Test. This is a basic result widely used in number theory and algebra so you should learn it asap. Aug 23, 2019 at 12:08
• OK, I've added a step-by-step explanation of your answer under the heading "Bill's approach" to make sure I've understood it. Let me know if you see any issues with it or if I made an incorrect assumption somewhere. Thanks again for your answer Bill! Sep 1, 2019 at 1:19
• @dharmatech Yes, your explanation and understanding is correct. Good work. Glad to help. Sep 1, 2019 at 16:33