Mod remainders of Biprimes and their factors

59 Views Asked by At

I would postulate the following:

Let $B$ be a biprime with two different odd factors $p$ and $q$

Then at least one integer n exists such that

$p\equiv x \pmod n$ and $q\equiv y \pmod n$ and $B \equiv (x*y) \pmod n$, holds true

where: $x$ and $y$ are either 1 or odd primes; $x*y <n$; $n <p$ and $n<q$; $n \equiv 0 \pmod 2$ and $n>2$.

My experimental research found at least one n for all of the biprimes between 1e11 and 1.001e11 where p/q<2. There were 21580 such biprimes, and 4 of these had only one n result. I searched between n=4 and n=B^0.5.

Can anyone provide any theoretical basis for the postulate?

1

There are 1 best solutions below

1
On

As mentioned above in comments, in order to have any valid $n$ we need $p,q>3$.

$n=4$ will always be a solution if either $p\equiv 1$ or $q\equiv 1 \bmod 4$ (although when $p\equiv q\equiv 3 \bmod 4$, $n=8$ is not a solution either). Similarly for $p,q>5$, $n=6$ will always be a solution if either $p\equiv 1$ or $q\equiv 1 \bmod 6$. So any counterexample will have $p,q\equiv 11 \bmod 12$.

You state in comments that $649 = 11\cdot 59$ is a counterexample, so let's look at that. Note that there are only four possible values for $n \in \{4,6,8,10\}$ and that we already know that $4,6$ and $8$ are not going to work. Then $(p,q)\equiv (1,9)\bmod 10$, which only fails due to the requirement for $y$ to be prime.

Without the prime requirement, of course you can always take $n=p{-}1$ (with $p<q$).