0
$\begingroup$

Below is my attempt to define a simple notation (ordered set of distinct prime factors) that can be used with the Chinese Remainder Theorem.

Please let me know if anything that I said is incorrect, unclear, or if there is a more standard way to make the same points.

  • Let $p_n$ be the $n$th prime.

  • Let lpf$(x)$ be the least prime factor of $x$.

  • Let $t > s$ be integers.

Definition 1: Ordered set of least prime factors:

Let $s,t$ represent a sequence of consecutive integers. The ordered set of least prime factors is the ordered set of prime numbers that correspond to the least prime factor of each integer that makes up the sequence.

Example: For $s=7,t=12$, the sequence of consecutive integers is: $8,9,10,11,12$. The ordered set of least prime factors for $s,t$ would be: $(2,3,2,11,2)$.

Definition 2: Implied Least Prime Factors:

There are two conditions where the least prime factor is implied:

(1) Existence Condition: For each prime $p$, there exists a sequence of integers $n_i$ such that given a sequence of $n_i$ consecutive integers, at least $i$ of the integers must have $p$ as its least prime factor.

The most obvious example of this is $p=2$ where each $n_i=2i$ (that is, $n_1 = 2, n_2=4, n_3=6, \dots$. For every sequence of $2i$ consecutive integers, $i$ must be even.

In the case of $p=5$, $n_1=20, n_2=30$. For every sequence of $20$ consecutive integers, at least one must have a least prime factor of $5$. For every sequence of $30$ consecutive integers, $2$ must have a least prime factor of $5$.

(2) Repetition Condition: If $p$ is the least ptime factor of $x+2$, then $p$ must also be the least prime factor of $x+p\#$ where $p\#$ is the primorial.

For example, $2\# = 2$ and $3\# = 6$. So if lpf$(c)=3$, it follows that lpf$(c+6)=3$ too.

Lemma 1: Ordered Set of Least Prime Factors and CRT

Given an ordered set of least prime factors that includes the implied ones from Definition 2 above, the Chinese Remainder Theorem can be used with the non-repeating least prime factors to find an $s,t$ that represent a sequence of consecutive integers that corresponds to the ordered set.

Argument:

(1) Let $(p_1, p_2, p_3, \dots, p_n)$ be an ordered set of primes.

(2) This ordered set corresponds to the following conditions which can be solved using the Chinese Remainder Theorem.

$$x \equiv -1 \pmod {p_1}$$ $$x \equiv -2 \pmod {p_2}$$ $$x \equiv -3 \pmod {p_3}$$ $$\dots$$ $$x \equiv -n \pmod {p_n}$$

(3) The repeating least prime factors can be ignored since they are implied.

Definition 3: Ordered set of odd least prime factors:

The ordered set of least prime factors includes $2$ for every other element. The ordered set of odd least prime factors is the ordered set of primes that corresponds to a given sequence of consecutive integers that only includes the odd primes.

Example: For $s=7,t=12$, the sequence of consecutive integers is: $8,9,10,11,12$. The ordered set of odd least prime factors for $s,t$ would be: $(3,11)$.

Since it is straight forward to convert the ordered set of odd least prime factors $(o_1,o_2,\dots,o_m)$ to the ordered set of least prime factors $(2,o_1,2,o_2,2,\dots,2,o_m,2)$, it follows that Lemma 1 applies to the ordered set of odd least prime factors as well.

Definition 4: Ordered set of distinct odd least prime factors:

The ordered set of odd least prime factors includes repeating least prime factors. For example for every $3$ odd least prime factors, at least one will be $3$. The ordered set of distinct odd least prime factors is the ordered set of primes that corresponds to a given sequence of consecutive integers that only includes the first instance of a least prime factor.

Example: For $s=7,t=22$, the corresponding ordered set sequence of odd least prime factors is: $(3,11,13,3,17,19,3)$. The ordered set of distinct odd least prime factors for $s,t$ would be: $(3,11,13,17,19)$.

Since it is straight forward to convert the ordered set of distinct odd least prime factors $(3,p_2,\dots,p_m)$ to the ordered set of odd least prime factors $(3,p_2,p_3,3,\dots,p_m)$, it follows that Lemma 1 applies to the ordered set of distinct odd least prime factors as well.

$\endgroup$
  • 1
    $\begingroup$ What are you trying to achieve? $\endgroup$ – Bill Dubuque Aug 6 '17 at 15:14
  • $\begingroup$ A concise notation for least prime factors. I want to clearly state that $(3,7,5,11)$ represents a set of conditions that are solvable by CRT. $\endgroup$ – Larry Freeman Aug 6 '17 at 15:16

Your Answer

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

Browse other questions tagged or ask your own question.