# Homework Help: Easy number theory problem

1. Feb 18, 2014

### chimath35

An integer is divisible by 9 if and only if the sum of its digits is divisible by 9

Proof by induction?

2. Feb 18, 2014

### chimath35

I am new to proofs never done them, I am stuck ac=b 9c=b ex. 9c=81 so c is an int. thus divisible let b= d+dn so 9c=d+dn then 9c=d+dn+dn+9

3. Feb 19, 2014

### hilbert2

In the decimal system, an integer with $n$ digits is written in the form
$\sum_{k=0}^{n-1}a_{k}10^{k}$, where the numbers $a_{k}$ are the digits.

Now consider the number
$\sum_{k=0}^{n-1}a_{k}10^{k}-\sum_{k=0}^{n-1}a_{k}$,
and deduce that it must always be divisible by 9. Then use the fact that if a sum of two integers, $m+n$ is divisible by 9 then either both $m$ and $n$ are divisible by 9 or neither of them is. That way you can prove the theorem.

4. Feb 19, 2014

### Curious3141

Have you worked with modulo notation? Easiest way is to reduce the decimal representation $\sum_{k=0}^{n-1}a_{k}10^{k} \pmod{9}$ where the digits $0 \leq a_k \leq 9$ and make the observation that $10 \equiv 1 \pmod{9}$. The rest should quickly follow, but if you get stuck, post back.

5. Feb 19, 2014

### kduna

This is a great hint. Using this method, you can actually prove a stronger statement:

$a \equiv (\sum a_k) \ (\text{mod } 9)$

where $a_k$ are the digits of $a$.