Is there a way to make (x mod p) mod q = x mod q possible?

Question

Is it possible to restrict $p$ and $q$ ($p, q \in primes$) in such a way that $(x$ mod $p)$ mod $q \equiv x$ mod $q$ always holds?

I actually need a looser condition:

I need that if $x \equiv 0$ mod $q$, then $x \equiv 0$ mod $p$ mod $q$.

Is the above mentioned condition (in bold) possible?

@D_S Can third isomorphism theorem be useful in deciding the kind of primes that possess this property? — AdveRSAry, May 26 '17 at 23:56
No, because if p < x < q then $(x \mod p) \mod q \not \equiv x \mod q$. — fleablood, May 27 '17 at 00:42
BTW (x mod p) as a number rather than an equivalence class is an abuse of definitions. — fleablood, May 27 '17 at 00:43

score 3 · Accepted Answer · answered May 27 '17 at 00:43

3

If $x \equiv 0 \mod q$, we have $x = kq$.

Now, for all integer $k$, we must have that $(kq \bmod p) \equiv 0 \mod q$.

However, as $q$ and $p$ are coprime $(kq \bmod p)$ takes on all residues $[0, p-1]$, so we see this is impossible.

answered May 27 '17 at 00:43

orlp

$k$ and $p$ could have a common divisor. – Χpẘ May 27 '17 at 00:56
@Χpẘ That doesn't matter. $k < p$ is sufficient to get all residues and since $p$ is prime that means no common divisor. – orlp May 27 '17 at 01:04
What if $x=npq$ (as suggested in another answer)? – Χpẘ May 27 '17 at 01:06
@Χpẘ The question isn't about finding an $x$ that works. but that for certain $p, q$ all $x$ work. – orlp May 27 '17 at 01:09

1 Answers1