# Why as $r$ increases, prime $p$ s.t. $\operatorname{ord} a=q^r$ (in mod $p$) also increases?

Let $$n$$ and $$a>1$$ be an integer and $$n=q_1^{r_1}\cdots q_s^{r_s}$$ is prime decomposition.

The book now I read(Gerald J.Janusz "Algebraic Number Fields") already prove following fact(Lemma 5.3).

Let $$a,r$$ be integers, each at least 2, and $$q$$ a prime integer. Then there exist a prime $$p$$ such that the multiplicative order of $$a$$ modulo $$p$$ is $$q^r$$.

So, the book says "For any $$r\geq r_i$$ and $$r\geq 2$$ there is a prime $$p_i$$ such that $$a$$ has order $$q_i^{r_i}$$"(maybe the book mistake $$q_i^r$$ for $$q_i^{r_i}$$)

Then the book says "As r increases, $$p_i$$ also increases and the order of $$a$$ mod $$p_i$$ is divisible by $$q_i^{r_i}$$". But I don't understand "As r increases, $$p_i$$ also increases". Would someone tell me?

• See also math.stackexchange.com/questions/3367689/… posted by the same user. Sep 24, 2019 at 6:40
• I have the book but I can't see where the lemma is ? This lemma in chapter one? Sep 25, 2019 at 16:54
• @Ameryr chapter five. Sep 26, 2019 at 6:05

I didn’t read this book and I don’t know what the author meant, so I thought as follows. It is possible that for given $$a$$, $$r$$, and $$q$$ there are several primes $$p$$ such that multiplicative order $$\deg_p a$$ of $$a$$ modulo $$p$$ is $$q^r$$. For instance, for $$a=13$$, $$r=2$$, and $$q=2$$, $$\deg_p a=q^r$$ that is $$\deg_p 13=4$$ both for $$p=5$$ and $$p=17$$. If we have to choose one $$p=p(r)$$ among such primes, it is natural to put $$p(r)$$ the smallest prime $$p$$ such that $$\deg_p a=q^r$$. But even in this case it can be $$p(r+1). For instance, for $$a=19$$ and $$q=2$$, we have $$p(2)=181$$, but $$p(3)=17$$.

You have $$a,r_i$$ and $$q_i$$ are fixed now there is a prime $$p_i$$ for each $$i$$ such that $$a^{q_i^{r_i} }\cong 1 (\mod p_i )$$ the book says if we consider $$r\geq r_i$$ then for any such $$r$$ there exists $$p$$ with $$a^{q_i^r}\cong 1 (\mod p)$$ and the statements follows if $$r$$ increases $$p$$ increases.

If you look at lemma 5.2 you will notice the book mean by $$a$$ have order $$q^r$$ mod $$p$$ is $$a^{q^r}\cong 1 (\mod p)$$ And $$\textbf{r}$$ is the least integer satisfying this not the least $$q^r$$. Now let $$r'=r+s$$ and suppose the order of $$a$$ mod $$p$$ is $$q^r$$ and mod $$p'$$ is $$q^{r'}$$ I want to show that $$p'>p$$ , $$a^{q^{r'}}=(a^{q^r})^{q^s}\cong 1 (\mod p')$$ keep in mind that $$p'$$ satisfying $$p'\mid a^{q^{r'}}-1 ,\; p'\nmid a^{q^{k}}-1: k And $$a^{q^{r'}}-1= (a^{q^{r}})^{q^s}-1=(a^{q^{r}}-1)P(a^{q^r})$$ I factored using $$x^n-1=(x-1)(x^{n-1}+\cdots 1)$$ in the last step where $$P$$ is a polynomial. So we have e $$a^{q^{r}}-1\mid a^{q^{r'}}-1$$ and we know that $$p'\nmid a^{q^{r}}-1$$ because $$r . I hope this helps you to figure why $$p

I will write the two lemmas in case somebody else can help

5.2 lemma: Let $$a$$ and $$r$$ be integers $$\geq 2$$ and $$q$$ a prime integer. There exists a prime $$p$$ such that $$a$$ has order $$q^r$$ modulo $$p$$.

Note in the proof the book pick $$p \mid X^{q-1} + X^{q-2} + \cdots + X+1$$ where $$X=a^{q^{r-1}}$$. Then proved that $$r$$ must be the least integer such that $$a^{q^r}\cong 1 \mod p$$ so it is not the normal multiplicative order.

5.3 Lemma: Let $$n=\prod_{i=1}^{s} q_i^{r_i}$$ be the prime factorization of $$n$$ as distinct primes. Let $$a>1$$ be an integer. There exists infinitely many square free integers $$m=p_1p_2\cdots p_sp'_1\cdots p_s'$$ such that the order of $$a$$ modulo $$m$$ is divisible by $$n$$.

The book begins the proof as the op mentioned above.

More ideas

Note that: $$a$$ is relatively prime with $$p$$ and $$p'$$ since $$a^{q^r} \equiv 1 (\mod p)$$ and $$a^{q^{r'}} \equiv 1 (\mod p')$$

Now by Euler theorem we have $$a^{p-1} \equiv 1 (\mod p)$$ and $$a^{p'-1}\equiv 1 (\mod p')$$

But $$r,r'$$ are the least integers such that $$a^{q^r}\equiv 1 (\mod p) , a^{q^{r'}} \equiv 1 (\mod p')$$ hence we have $$q^{r'} \mid p'-1$$ and $$q^{r} \mid p-1$$.

• Then why if $r$ increases $p$ increases? Sep 21, 2019 at 17:01
• @user682141 I edited my answer Sep 28, 2019 at 12:10
• Then why $p<p'$ at last? Sep 29, 2019 at 3:11
• I think it is normal multiplicative order because the order must be the form $q^i$ Sep 29, 2019 at 3:13
• Okay I see you are right because the order should divides $q^r$ so it is on the form $q^i$ for some $i$ Sep 29, 2019 at 16:44