4
$\begingroup$

I am currently reading the paper "PRIMES is in p" and have come across some notation that I don't quite understand in this following sentence

Consider a prime $q$ that is a factor of $n$ and let $q^k || n$. Then...

What does the notation $q^k || n$ mean here?

The full paper can be found here and the notation described above is used in the proof on page 2

$\endgroup$
  • $\begingroup$ Well I use this as a symbol of representing concatenation, for which $$a\mid\mid b = \left\{10^na + b : b\text{ has $n$ digits}\right\}.$$ but since we have $a = q^k$ and $b = n$ with $q$ being raised to an exponent $k$, then this notation would be different from how I know it to be defined, for all $k > 1$. $\endgroup$ – user477343 Feb 19 '18 at 15:19
11
$\begingroup$

Typically, that $q^k$ divides $n$ but no higher power of $q$ does.

$\endgroup$
  • $\begingroup$ Another way of writing it is $v_q(n)=k$ $\endgroup$ – G Tony Jacobs Feb 19 '18 at 15:16
  • $\begingroup$ @GTonyJacobs why is $v$ included? How do we even say this? With the two lines $\mid\mid$ then pursuant to one of the answers above, this is read as divides exactly but how would we read the equation, $v_q(n) = k$? $\endgroup$ – user477343 Feb 19 '18 at 15:20
  • $\begingroup$ The '$v$' stands for 'valuation'. For a prime $p$, the $p$-adic valuation of a number is a measure of how many powers of $p$ go into the number. What I wrote above says that the $q$-adic valuation of $n$ is $k$. Example: odd integers have a $2$-adic valuation of $0$. Integers such as $2,6,10$, which are $2$ times an odd integer, have a $2$-adic valuation of $1$. A number such as $96$, which we can divide by $2$ five times before reaching an odd number, would have a $2$-adic valuation of $5$. $\endgroup$ – G Tony Jacobs Feb 19 '18 at 15:24
  • $\begingroup$ It's a nice concept for talking about how the integers interact with a specific prime, and it extends to all rational numbers: $\frac54$ has a $2$-adic valuation of $-2$. $\endgroup$ – G Tony Jacobs Feb 19 '18 at 15:25
4
$\begingroup$

It means "divides exactly" in the sense that $q^{k+1}$ does not divide n.

$\endgroup$
2
$\begingroup$

It means that $k$ is the higher power that divides $n$. In other words: $$q^k\|n\iff q^k|n\wedge q^{k+1}\nmid n$$

$\endgroup$

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.