# Easy number theory problem

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

Proof by induction?

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

hilbert2
Gold Member
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.

1 person
Curious3141
Homework Helper
An integer is divisible by 9 if and only if the sum of its digits is divisible by 9

Proof by induction?

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.

1 person
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.

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

1 person