Hey there! Let's clear up that notation from PRIMES is in P — it's a standard number theory symbol that's super useful in factorization arguments like the one in the paper's proof on page 2.

The notation $q^k || n$ is called the exact divisibility symbol, and it bundles two key meanings together:

• First, $q^k$ divides $n$ (written formally as $q^k \mid n$), meaning you can divide $n$ by $q^k$ and get an integer result.
• Second, $q^{k+1}$ does NOT divide $n$ (written as $q^{k+1} \nmid n$), so you can't divide $n$ by one extra factor of $q$ without getting a non-integer.

Put simply, this tells you that $k$ is the highest power of the prime $q$ that divides $n$. For example, if $n = 18 = 2^1 \times 3^2$, then $2^1 || 18$ and $3^2 || 18$.

In the context of the paper's proof, when they state "考虑素数$q$是$n$的一个因子，令$q^k || n$", they're just defining $k$ as the exponent of the prime $q$ in $n$'s prime factorization — this is a common setup when working with divisors and modular arithmetic in primality tests.

内容的提问来源于stack exchange，提问作者M Smith