0
$\begingroup$

I am trying to understand a paper where a numerical algorithm is described. I do not understand the point where the expression "exact power of a prime that divides a number" is used. Here is the text with all related context and the exact point in bold:

Let $n_0$ be a fixed (small) positive integer, and $n≥4n_0$ (...)

Let $m$ be a positive integer

  1. Compute the prime factors $p_1$, . . . , $p_l$ of $m$
  2. For index $j$, $1≤j≤k$, perform the following operations :
    1. Assign $a = n − j + 1$ and $b =j$.
    2. Decompose $a$ and $b$ with the powers of $p_i$, in the form $$a=a^{*}×p_1^{α_1}...p_l^{α_l}, b=b^{∗}×p_1^{β_1}...p_l^{β_l}$$ For each $i$, $p_i^{α_i}$ is the exact power of $p_i$ that divides $a$, $p_i^{β_i}$ is the exact power of $p_i$ that divides $b$, so that $a^∗$ and $b^∗$ do not have one of the $p_i$ as a prime factor.

What I am struggling to understand is that the $p$ prime number is a factor of $m$ but not necessarily of $a$. The definition of $p_i^{\alpha_i}$ calls for an exact division of $a$, not the largest power that is not greater than $a$.

For instance

$$ n_0 = 2 \rightarrow n = 4n_0 = 8 \\ m = 21 \rightarrow p_1 = 3; p_2 = 7 \\ j = 1 \rightarrow a = 8 - 1 + 1 = 8; b = 1 \\ p_1^{\alpha_1} = 8 / 3^{\alpha} $$

where the last expression does not seem to have an exact (integer) solution.

Am I misunderstanding the definition of "exact division"? Or am I missing something in the algorithm steps leading to this point?

Any help is appreciated.

$\endgroup$
2
$\begingroup$

The exact power here means the maximal power that divides the number.

So the exact power of $5$ that divides $50$ is $2$ as $5^2$ divides $50$ while $5^3$ does not.

If a primes does not divide a number the exact power that divides it is the $0$-th power.

$\endgroup$
  • $\begingroup$ Yes, I started to suspect this was the case as soon as I finished writing the question :) Just for clarification: is this a conventional meaning of "exact division"? I found an unrelated definition in Wikipedia and my initial assumption in a mathematical software library $\endgroup$ – logc Feb 25 '15 at 13:56
  • $\begingroup$ I would not say it is a usage of "exact division." The phrase is "the exact power of [something] that divides" in that usage it is somewhat common. A notation is $p^a||n$ (so twice the symbol for division). Yet I would consider variations on the phrase like say "we have $5^2$ divides $50$ exactly" or "the divsion of $50$ by $5^2$ is exact" as confusing precisely for the reason you mention (the second usage). $\endgroup$ – quid Feb 25 '15 at 14:02
  • $\begingroup$ After re-reading the whole context, it seems the operation is in fact focused on "weeding out" prime factors, and not finding exact powers that may not exist. So, I'm accepting your answer. Thanks! $\endgroup$ – logc Feb 25 '15 at 14:20
  • $\begingroup$ You are welcome. Yes, the point is to factor out all instances of $p$ that are present, so that the co-factor is not divisible by $p$. $\endgroup$ – quid Feb 25 '15 at 14:22

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.