1
$\begingroup$

Let:

  • $p_1, p_2$ be primes
  • $x > 0$ be an integer where $p_1 \nmid x$ and $p_2 \nmid x$

I am interested in understanding the conditions where:

  • $x - p_1 \equiv 0 \pmod {p_2}$
  • $x - p_2 \equiv 0 \pmod {p_1}$

It seems to me that this is only true when:

$$x - p_1 - p_2 \equiv 0 \pmod {p_1p_2}$$

I find this interesting because I can apply this to arguments about primes.

Here are some very simple examples:

Since $5\times 3 \nmid 56 - 5 - 3 = 48$, either $(56 - 5)$ or $(56 - 3)$ must be prime.

Since $7\times 3 \nmid 110 - 7 - 3 = 100$, either $(110-3)$ or $(100-7)$ must be prime [in this case, both are]

I suspect that either my reasoning is wrong or this property is well known.

When I read the article on modular arithmetic in Wikipedia, I am not seeing anything related to this property.

Most likely, this property can easily be derived from one of the properties mentioned there. If someone could explain the related property, that will help me know where to look to learn more. :-)

$\endgroup$
4
  • 1
    $\begingroup$ As how I see it, it isn't something very frequent, but it looks like something anyone could infer. If you notice that $p_i\equiv 0 \pmod{p_i}$ for both $i=1,2$ you can state that $x-p_i-p_j\equiv 0 \pmod{p_i}$, and the product will still mantain the modular equality since $p_1,p_2$ are primes. $\endgroup$
    – iam_agf
    Jun 1, 2020 at 23:50
  • 1
    $\begingroup$ Thanks for your answer. While the property is something anyone could infer, if it is valid, I suspect that there are some interesting conclusions that can be reached using it. :-) I could be wrong. If my intuition is right, I'll add some more advanced examples. $\endgroup$
    – Larry Freeman
    Jun 1, 2020 at 23:56
  • $\begingroup$ Your question is that if $p_1p_2\nmid x-p_1-p_2$, then $x-p_1$ or $x-p_2$ is prime? $\endgroup$
    – iam_agf
    Jun 2, 2020 at 0:11
  • $\begingroup$ Not exactly. Let me explain my example. In the case of $56$, if we only consider primes less than $\sqrt{56}$, the only possible divisors are $2,3,5$. Since $3,5$ are relatively prime $56$, only $3$ or $5$ can divide $56 - 3$ and $56-5$. Likewise, for $110$, the only primes to consider are $2,3,5,7$. Since $2,5$ divide $110$, the only possible divisors for $110 - 3$ is $7$ and $110-7$ is $3$. Does that explain my reasoning? $\endgroup$
    – Larry Freeman
    Jun 2, 2020 at 0:34

1 Answer 1

Reset to default
2
$\begingroup$

Assuming $p_1$ and $p_2$ are distinct primes, you have a system of two linear congruences with coprime moduli. There exist integers $a$ and $b$ such that $ap_1+bp_2=1$.

The Chinese remainder theorem gives a constructive formula for a solution $x$, (unique modulo $p_1p_2$), as $x=ap_1^2+bp_2^2$. This can be rewritten as $$ x=p_1(1-bp_2)+p_2(1-ap_1) $$ from which it follows that $x\equiv p_1+p_2\pmod{p_1p_2}$.

Conversely, if $x\equiv p_1+p_2\pmod{p_1p_2}$, it is immediate that $x\equiv p_1\pmod{p_2}$, and $x\equiv p_2\pmod{p_1}$.

$\endgroup$
1
  • 2
    $\begingroup$ Thanks very much! I wasn't thinking about the property in terms of CRT. That really sets the proper context for my question! $\endgroup$
    – Larry Freeman
    Jun 2, 2020 at 0:36

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.