Why is it that "If 3 cannot divide "q" there will be a remainder of 1 or 2"?

Question

I am studying proofs in discrete math and I ran into this statement that "If 3 cannot divide "q" there will be a remainder of 1 or 2". I know that this is some pretty basic stuff but I am having a hard time to catch the concept of remainders.

What exactly is the definition of a remainder?

Can I conclude from this statement that if "4" cannot divide "q" there will be a remainder of 1,2 or 3?

Thanks

Yes your conclusion is true. – derivative Dec 02 '13 at 23:33 — derivative, Dec 02 '13 at 23:33

score 4 · Answer 1 · answered Dec 02 '13 at 23:34

4

The division algorithm on the natural numbers states that for all $a,b\in \Bbb N$ ($\in$ means "in", $\Bbb N$ is all integers greater than $0$), there exist $q,r\in\Bbb N\cup\{0\}$ such that $a=bq+r$ and $0\le r<b$. The $r$ here is how you define a remainder.

Using this:

If we are dividing $a$ by $3$, the remainder, $r$, has the restriction $0\le r<3$. But if we say that $a$ is not divisible by $3$, then $r\neq 0$, so the only possible values of $r$ are $1$ and $2$.

You can apply a similar argument to $b=4$, yes.

answered Dec 02 '13 at 23:34

Tim Ratigan

7,247

Thanks! Your answer made it super clear – Reboot_87 Dec 02 '13 at 23:40
1

So the restriction 0<r<b is to make sure we wouldn't surpass the original number? – Reboot_87 Dec 02 '13 at 23:44
1

Yeah. You'll notice that if $r=b$ then we have $a=bq+b=b(q+1)+0$, so we could have a smaller $r$. – Tim Ratigan Dec 02 '13 at 23:49

score 2 · Answer 2 · answered Dec 02 '13 at 23:40

Remainder is what is left when you make integer division. In equations: Say you want to divide $p$ by $q$. You can always find an integer $m$ and an integer $0\le r<q$ such that $$p=m\cdot q+r$$ or equivalently $$r=p-m\cdot q$$

$r$ here is your remainder. For instance if you want to divide $p=25$ by $q=3$, you can realize that it the answer is a bit more than $8$ but less than $9$ since $3\cdot8=24<25$ and $3\cdot9=27>25$. With this you can choose $m=8$ and write $25 = 8\cdot 9 + 1$. This means that the remainder of $25$ when divided by $3$ is $1$.

Because of the restriction $0\le r<q$, then when you divide by $q=3$ the possible remainders are: $0,1,2$. If $p$ is a multiple of $3$, by definition, then the remainder must be $0$. Hence only remainders $1$ and $2$ are possible if $p$ is not a multiple of $3$, or in other words, if $3$ does not divide $p$

score 0 · Answer 3 · answered Dec 02 '13 at 23:36

You can write all integers in regards to a particular modulus; In other words, if you are looking to show that "if 3 can not divide q, then the remainder is either 1, or 2", you can show that integers can be written: $$3k$$ $$3k+1$$ $$3k+2$$ For example, if k=0, the above numbers will be $0, 1, 2$. So it's not a stretch to see that $$3k+3=3(k+1)$$ $$3k+4=3(k+1)+1$$ $$3k+5=3(k+1)+2$$ Letting k=0 still produces the next three numbers $3, 4, 5$. So can write all integers in one of the above forms which means that if 3 doesn't divide it, it has a remainder of 1 or 2.

Why is it that "If 3 cannot divide "q" there will be a remainder of 1 or 2"?

3 Answers3