Why is it that "If 3 cannot divide "q" there will be a remainder of 1 or 2"? 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 
 A: 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.
A: 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$ 
A: 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.
