A positive integer is divisible by $3$ iff 3 divides the sum of its digits I am having trouble proving the two following questions: 


*

*If $p|N$, $q|N$ and gcd(p,q)=1, then prove that $pq|N$

*If $x$ is non zero positive integer number, then prove that $3|x$ if and only if 3 divides the sum of all digits of $x$.
For both questions I tried to use theorems of discrete mathematics, but I could not find the way to solve them.
 A: (1)  The hypotheses $p|N$ and $q|N$ give us two integers $m,k$ so that $N=mp$ and $N=kq$.  This implies $mp=kq$ so that $q|mp$.  Now, since $gcd(p,q)=1$ and $q|mp$ we know that $q|m$ (think about why this is true if it's not clear).  Then  $m=sq$ for some integer $s$.  Putting this all together, we have $N=mp=sqp=s(pq)$ so $pq|N$.
(2) Here we have an if and only if statement so you'll have to prove two statements/directions(or both at once):
(i) if $3|x$ then $3$ divides the sum of the digits of $x$
(ii) if $3$ divides the sum of the digits of $x$ then $3$ divides $x$
The strategy is to write the number in base $10$, for example (not a proof):
$1356=1\cdot 10^3+3\cdot 10^2+5\cdot 10^1 + 6\cdot 10^0$
Now $10$ has remainder $1$ under division by $3$ so the remainder of $1356$ under division by $3$ is $1 \cdot 1^3 + 3\cdot 1^2 +5\cdot 1^1 +6\cdot 1^0=1+3+5+6$ which is exactly the sum of the digits.  Then the remainder under division by $3$ of $1356$ and $1+3+5+6$ are the same, and $3|1356$ if and only if $3|1+3+5+6$.  
Try to do this in general for some number $n$ with logical steps following the idea of the example above to write a formal proof.
A: Here is an explanation of number 2. We will use a corollary from a theorem (both taken from Rosen's Discrete Mathematics text.

Theorem: Let $m$ be a positive integer. If $a\equiv b \text{ mod } m$ and $c\equiv d \text{ mod } m,$ then
  $$
a+c \equiv b+d \text{ mod } m \qquad\text{and}\qquad ac \equiv bd \text{ mod } m.
$$

From this theorem we get this corollary

Corollary: Let $m$ be a positive integer and let $a$ and $b$ be integers. Then
  $$
(a+b) \text{ mod } m = ((a \text{ mod } m) + (b \text{ mod } m)) \text{ mod } m
$$
  and
  $$
ab \text{ mod } m = ((a \text{ mod } m)(b \text{ mod } m)) \text{ mod } m.
$$

Note that "$\equiv$" is used to indicate congruence, while "=" is used to indicate equality. 
The problem says: If $x$ is a non zero positive integer number, then prove that $3|x$ if and only if $3$ divides the sum of all digits of $x$.
We can represent $x$ as sum like so
$$
\begin{aligned}
x &= a_n\cdot 10^n + a_{n-1}\cdot 10^{n-1} + \cdots + a_1\cdot 10^{1} + a_0\cdot 10^0\\
&= \sum_{k=0}^n a_k10^k,
\end{aligned}
$$
where $a_0$ is in the ones place in $x$, $a_1$ is in the tens place in $x$, $a_2$ is in the hundreds place in $x$, etc $\dots$ Note that $3|x$ implies that $0 = x\text{ mod } 3.$ Then,
$$
\begin{aligned}
0 &= x\text{ mod } 3\\
&=\left(\sum_{k=0}^na_k10^k\right)\text{ mod } 3 &&\text{substitute}\\
&=\left(\sum_{k=0}^n(a_k10^k\text{ mod } 3)\right)\text{ mod } 3 &&\text{ by corollary}\\
&=\left(\sum_{k=0}^n([(a_k\text{ mod } 3)(10^k\text{ mod } 3)]\text{ mod } 3)\right)\text{ mod } 3 &&\text{ by corollary}\\
&=\left(\sum_{k=0}^n([(a_k\text{ mod } 3)(1\text{ mod } 3)]\text{ mod } 3)\right)\text{ mod } 3 &&1 \equiv 10^k\text{ mod }3\\
&=\left(\sum_{k=0}^n(a_k\text{ mod } 3)\right)\text{ mod } 3 &&(a_k)(1)=a_k\text{ and  corollary}\\
&=\left(\sum_{k=0}^na_k\right)\text{ mod } 3 &&\text{by corollary.}\\
\end{aligned}
$$
The last equality states
$$
0 = \left(\sum_{k=0}^n a_k\right)\text{ mod }3,
$$
which proves that $3$ divides the sum of all digits of $x$. To prove the other direction (if $3$ divides the sum of all digits of $x$, then $3|x$) just use the same equalities, but start at the bottom and work your way to the top.
A: $x=a_0+10a_1 + 100a_2 + \cdots+10^{n}a_{n}$.
Let $s$ be the sum of all the digits of $x$, that is $s=a_0 + a_1 + a_2 +\cdots a_n$.
$x-s = 9a_1 + 99a_2 + \cdots(10^{n}-1)a_n$.
Clearly $3\vert x-s$. If $3\vert s$, then $3\vert x$. If $3\vert x$, then $3\vert s$. 
Therefore $3|x$ if and only if $3$ divides the sum of all the digits of $x$.
A: For (2), this is “casting out nines”, which used to be taught, and ought still to be taught, in elementary-school mathematics. It’s a matter of congruence modulo $9$, since $10\equiv1\pmod9$, we also have $10^n\equiv1\pmod9$, so that a number whose decimal representation is $d_md_{m-1}\cdots d_2d_1d_0$ is congruent to 
$d_m+d_{m-1}+\cdots+d_2+d_1+d_0$ modulo $9$ (the $d$’s are the decimal digits). The result follows.
A: Hints.
(1) Use the definitions. What does it mean for an integer to divide another? What does it mean for two integers to be relatively prime? Do you know that the $\text{GCD}$ of two integers may be expressed as integral linear combinations of these integers?
(2) Just expand the number out in powers of $10$ in the usual decimal convention. Then note that any positive power of $10$ reduces to $1$ modulo $3.$ Can you see why the rule for divisibility for $3$ and $9$ are similar?
