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. 🙂
Best Answer
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}$.