[Math] A positive integer is divisible by $3$ iff 3 divides the sum of its digits

divisibilityelementary-number-theory

I am having trouble proving the two following questions:

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

  2. 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.

Best Answer

(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.

Related Question