1
$\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$
3
  • 1
    $\begingroup$ What are you trying to achieve? $\endgroup$ Aug 6, 2017 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$ Aug 6, 2017 at 15:16
  • $\begingroup$ @LarryFreeman FYI, there's a minor issue in what you wrote of "... the Chinese Remainder Theorem can be used with the non-repeating least prime factors to find an $s,t$ ...". Note the Chinese remainder theorem is technically just an existence theorem, i.e., it proves a unique solution exists, but not how to find it. To actually find a solution, you need to use a method like the Extended Euclidean algorithm instead. $\endgroup$ Jul 26, 2020 at 8:13

1 Answer 1

1
$\begingroup$

First, there's a couple of small mistakes in what you wrote in

(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.

"ptime" should be "prime". Also, $x + 2$ should be $x$. This then works since $p$ also divides $x + p\#$, with all primes smaller than $p$ dividing $p\#$ but not dividing $x$, so they don't divide $x + p\#$. This means the least prime factor of $x + p\#$ is also $p$.

However, secondly and more importantly, although you have an interesting idea & methodology, there's a significant concept missing from your Lemma $1$. This is if there are any primes less than the largest prime of the list of non-repeating least prime factors which are not included in the list, then the smallest positive solution of the set of congruences (e.g., determined by using the Extended Euclidean algorithm or some other method such as by inspection for simpler cases) may be incorrect due to one of those missing primes being a factor of an integer which is supposed to have a larger least prime factor.

A relatively simple example is to consider the least prime factors being $(11, 2, 3)$. You then have the congruence equations of

$$x \equiv -1 \pmod{11} \tag{1}\label{eq1A}$$

$$x \equiv -2 \pmod{2} \tag{2}\label{eq2A}$$

$$x \equiv -3 \pmod{3} \tag{3}\label{eq3A}$$

The solution is

$$x \equiv 54 \pmod{66} \tag{4}\label{eq4A}$$

Note, though, using $s = 54$ and $t = 57$ gives the consecutive integers of $55$, $56$ and $57$, so the least prime factors are $(5, 2, 3)$. However, adding $66$ to get the next congruence value, i.e., using $s = 120$ and $t = 123$ instead, does work.

I've thought about how to handle this issue, but I haven't determined any good general solution. One method is to keep adding the product of all of the non-repeating least prime factors until you get a valid solution, which I'm quite certain will always work as long as your set of least prime factors is valid. However, there's no easy or general way, that I know of, to determine how many times this product would need to be added.

Another method is to add modulo conditions for each of the missing primes to ensure the result is successful. The issue then is determining what specifically to add. One way is to add a set of modulo inequalities to state that for each least prime factor which has smaller missing primes that none of them are congruent to $0$ (e.g., $x + 1 \not\equiv 0 \pmod{2}$). However, there's no algebraic method I know of to solve these inequalities, plus in general there's not even a guarantee a solution exists (e.g., $x + 2 \not\equiv 0 \pmod{2}$ and $x + 3 \not\equiv 0 \pmod{2}$ has no solutions), although this shouldn't be a problem in your case.

Instead, you can try adding modulo equalities. For any missing primes $p \gt n$, you can just simply use $x \equiv 0 \pmod{p}$. For the smaller missing primes, any modulo condition to handle them needs to ensure each value which corresponds to a multiple of that prime in $[x + 1, x + n]$ must also have a smaller prime factor which is in the list of least prime factors. For fairly small $n$, this can just be determined manually. However, I don't know offhand of any algebraic method that works for all sets of integers, no matter how small or large.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .