Let $p$ be a prime and $n$ a positive integer not divisible by $p$. When working on a fixed field in the cyclotomic field $Q(e^{2i\pi/n})$, I tumbled into the condition: $p$ does not divide $\frac{\phi(n)}{\mathrm{ord}(n)},$ where $\phi(n)$ is Euler's totient function, and $\mathrm{ord}(n)$ is the multiplicative order of $p$ mod $n$. That is, $\mathrm{ord}(n)$ is the smallest positive integer $k$ such that $p^k \equiv 1 (\bmod n)$. I would appreciate very much if you could provide some examples for this condition to be satisfied. A family (in either $p$ or $n$) of examples is even nicer.
Euler’s Totient Phi and a Prime – Number Theory
nt.number-theory
Best Answer
Below I write $\mathrm{ord}(x) $ for $\mathrm{ord}_x(p)$. As usual, $\nu_p(t)$ denotes the maximal $m$ for which $p^m$ divides $t$.
Let $n=\prod q_i^{\alpha_i}$ be a prime factorization of $n$. Then $\nu_p(\phi(n))=\sum_i \nu_p(q_i-1)$. On the other hand, $\mathrm{ord}(n)=\mathrm{lcm} \{\mathrm{ord}(q_i^{\alpha_i}):i=1,2,\ldots\}$. Since $\mathrm{ord}(q_i^{\alpha_i})$ divides $\phi(q_i^{\alpha_i})=(q_i-1)q_i^{\alpha_i-1}$, we get $\nu_p(\mathrm{ord}(n))\leqslant \max_i \nu_p(q_i-1)$.
Therefore, if there exist at least two indices $i$ for which $p$ divides $q_i-1$, we get $\nu_p(\mathrm{ord}(n))<\nu_p(\phi(n))$, and your condition does not hold.
If $p$ divides no $q_i-1$, then your condition obviously holds as $p$ does not divide even $\phi(n)$ itself.
So, the interesting case to consider is when there exists unique $i$ for which $p$ divides $q_i-1$. Say, $q_i=1+p^Ab$, where $p$ does not divide $b$ (and $A>0$). Then your condition holds if and only if $p^A$ divides $\mathrm{ord}(q_i^{\alpha_i})$. Note that $\mathrm{ord}(q_i)$ divides $\mathrm{ord}(q_i^{\alpha_i})$, and the ratio is a certain power of $q_i$ (indeed, $q_i$ divides $p^r-1$, where $r=\mathrm{ord}(q_i)$, hence $q_i^2$ divides $p^{rq_i}-1=(p^r-1)(1+p^r+\ldots+p^{r(q_i-1)})$ and therefore $\mathrm{ord}(q_i^2)$ divides $rq_i$, and so on. This argument is an easy version of the so called Lifting the Exponent Lemma).
Thus, your condition holds if and only if $p^A$ divides $\mathrm{ord}(q_i)$, in other words, if $q_i$ does not divide $p^{(q_i-1)/p}-1$. Or, in yet other words, if $p$ is not a $p$-th power modulo $q_i$.
I doubt that there is a good characterization of such pairs $(p,q_i)$. If $p=2$, this holds if and only if $2$ is not a quadratic residues modulo $q_i$, that is, $q_i$ is congruent to 3 or 5 modulo 8.