Easy number theory problem

  • Thread starter chimath35
  • Start date
  • #1
110
0
An integer is divisible by 9 if and only if the sum of its digits is divisible by 9

Proof by induction?
 

Answers and Replies

  • #2
110
0
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
hilbert2
Science Advisor
Insights Author
Gold Member
1,529
551
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
Curious3141
Homework Helper
2,850
87
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.
 
  • #5
52
7
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##.
 

Related Threads on Easy number theory problem

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
737
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
0
Views
810
  • Last Post
Replies
3
Views
573
  • Last Post
Replies
1
Views
482
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
Top