11

I'm working through a practice test with no available solutions, and I came across this question.

Let $a,b,c,d,e$ be integers with $c>0$. Suppose that $a\equiv b\pmod c$, and that $d\equiv e\pmod c$. Determine whether each of the following statements are True or False.

i) $c\mid(a-b)$

ii) $c\mid(d-e)$

iii) $a+b\equiv d+e \pmod c$

My first question is this: why the parentheses around the modulo? Is there a meaningful difference between $a\mod b$ and $a \pmod b$? I assume not, but the latter kind of makes it look like "mod" is a unary operator.

Second, how do I interpret the use of "|"? I naturally thought of it as a logical "or", and evaluated the expressions like the C compiler might. Since $c$ is always greater than $0$, both the first two statements will always evaluate to "true".

In the third statement, each side of the equation is independent from the other, so there is no equivalency and it must evaluate to "false".

Am I anywhere close to the correct approach? The unfamiliar notation kind of threw me.

As several have guessed in the comments, it seems my confusion stemmed from the fact that I'm a programmer trying to brush up on his math skills, and not a student of number theory or modular arithmetic. Thanks to the comments and answers, I found this wikipedia article which also helped to clarify things.

Thanks guys!

Community
  • 1
stett
  • 369
  • 1
    First of all, $\pmod b$ doesn't apply to a single value $a$, but rather to the $\equiv$ symbol - it is telling you what the equivalence relation is. For example, $11\equiv (18\mod 7)$ doesn't make sense - what does $18\mod 7$ mean? Can we write $(12\mod 8)\equiv (18\mod 7)$? The point of $\pmod b$ is to determine a context. – Thomas Andrews Dec 23 '14 at 03:34
  • 2
    $\mid$ is definitely not logical or. That's computer notation. It is a relation operator, so you'd never write $(a\mid b)+c$, because $a\mid b$ evaluates to "true" or "false," not to a value. It is not uncommon to write $(a+b)\mid (c+d)$, but sometimes we skip if the complex format is on the right: $a\mid c+d+e$. – Thomas Andrews Dec 23 '14 at 03:38
  • You might want to see if you can find some material on the definitions relevant to elementary number theory and modular arithmetic; unfortunately, mathematicians and programmers are likely to disagree about what symbols mean. (That "might" should be taken as a "definitely should") – Milo Brandt Dec 23 '14 at 03:41
  • If your course/source is not defining these terms, you've got bigger problems. It shouldn't be hard to find the definition of $x\mid y$ in your book or notes? (It means that $x$ is a divisor of $y$ - that is, there is an integer $z$ so that $xz=y$.) – Thomas Andrews Dec 23 '14 at 03:44
  • You've basically fallen into a computer programmer's view of how symbols work. From a programmer's persective: $a\equiv b\pmod c$ is actually a ternary function $f(integer,a,integer,b,integer ,c)$ returning true or false, where $f(a,b,c)$ returns true if $a-b$ is divisible by $c$, and false otherwise... – Thomas Andrews Dec 23 '14 at 03:53
  • @ThomasAndrews To a programmer, $18\bmod 7$ (or 18 % 7) does make sense, and is equal to $4$. Since OP mistook $a\mid b$ as $a \vee b$, I think this is a probable. – peterwhy Dec 23 '14 at 04:07
  • Which is why I said he was thinking like a programmer, and misreading $a\equiv b\pmod c$. @peterwhy – Thomas Andrews Dec 23 '14 at 04:08
  • @ThomasAndrews - so then are these two statements equivalent: $a\equiv b\pmod c$ and $c|(a-b)$? If they are, I believe I understand what's going on. – stett Dec 24 '14 at 03:00

2 Answers2

8

The $|$ operator represents divisibility, not logical OR. $a \mid b$ is shorthand for $a$ divides $b$. As for your first question, $a$ mod $b$ represents the remainder when $a$ is divided by $b$ but $a_1 \equiv a_2 \pmod b$ the $\pmod b$ modifies the equivalence relation.

sayantankhan
  • 2,397
5

Just a linguistic addition: the statement “$a\equiv b\pmod m$” was originally read (and some of us still read it) as “$a$ is congruent to $b$ modulo $m$”. It’s Latin, and “modulo” means “with respect to the modulus”. You should think of the the “$\!\!\pmod m$” as an adverb telling you in what way $a$ is congruent to $b$.

Lubin
  • 62,818