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
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$.
No comments:
Post a Comment