Is $p \equiv q\pmod{15}$ the same as $p\equiv q\pmod{5}$?

Question

Let $p$ and $q$ be prime. If $p\equiv q \pmod{15}$, then is it true to say they are congruent mod $5$?

I figure I could say $p - q \equiv 0 \pmod{15}$, so $p\equiv q \pmod{5}$, but what throws me off is when we let $p = 37$ and $q = 7$.

So $37\equiv 7 \pmod{15}$, but $37\equiv 2 \pmod{5}$ which disproves this, doesn’t it? Or is it legal to just say $37\equiv 7 \pmod{5}$ is the same as $37\equiv 2 \pmod{5}$ since $7\equiv 2 \pmod{5}$.

Answer 1

You may be confusing the notion of modular equivalence in mathematics with the mod operator in computer programming; while the two are closely related, they're not quite the same thing. The mod operator is actually a function, one that takes two numbers (a value and a modulus) and returns the remainder from dividing the value by the modulus; for instance, we say that 22 mod 5 = 2. Here (ignoring negative numbers), a mod n = b means that c is a number between $0$ and $n-1$ and that $a-b$ is a multiple of $n$.

Mathematically, though, mod is generally used for what's known as an equivalence relation; we say that $a\equiv b\pmod n$ if and only if $a-b$ is a multiple of $n$. There's no requirement that $b$ be less than $n$; it's true that $22\equiv 2\pmod 5$, but it's also true that $22\equiv 37\pmod 5$ (since $22-37=-15$ is a multiple of $5$, or even that $22\equiv -13\pmod 5$ (since $22-(-13)=35$ is a multiple of $5$). The two can be related back and forth: in one direction we have $a\equiv b\pmod n$ if and only if $a$ mod $n = b$ mod $n$, and going the other way the value of $a$ mod $n$ is the unique number $b$ (can you see why it's unique?) such that $a\equiv b\pmod n$ and $0\leq b\leq n-1$.

Answer 2

$p \equiv q \bmod{15} \iff 15 \mid (p-q) \iff 5 \mid (p-q)$ and $3 \mid (p-q) \iff p \equiv q \bmod{3}$ and $p \equiv q \bmod{5}$.

Answer 3

I find it helpful to take questions like these out of a congruence relation to understand them sometimes. $p\equiv q\pmod{15}$ just means $p=q+15n$ for some integer $n$. This can now be rewritten as $p=q+5(3n)$. Since $3n$ is clearly also an integer, we can now put this back into a congruence relation $p\equiv q\pmod{5}$. Therefore it is true that $p\equiv q\pmod{15}$ implies $p\equiv q\pmod{5}$.

Also, you mentioned using the form $p-q\equiv0\pmod{15}$. I find this form is always preferable because it removes any confusion over the residue classes. Using your example where $p=37$ and $q=7$, it can be seen that $37-7=30\equiv 0\pmod{15}$ and $37-7=30\equiv 0\pmod{5}$.