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?

Edit This is also by me An problem in elementary number theory used for proving Artin's lemma(class field theory)


2 Answers 2


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)<p(r)$. 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<r'$$ 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<r'$ . I hope this helps you to figure why $p<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 $.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.