Direct Proof question

[jbower]

Hello all. I'm working on a proof and I'm needing a little help in the right direction. The statement to prove (via a direct proof) is:

For any positive integer n, n is a multiple of 9 if and only if the sum of the digits of n is a multiple of 9.

Here's what I have so far, but I think I'm making a mistake along the way:

Proof:
There exists a positive integer n that is a multiple of 9 if an d only if the sum of the digits of n is a multiple of 9.

(I will want to prove this using a direct proof)
If n is a multiple of 9, I can express this as 9n.
If the sum of the digits of n is a multiple of 9, I can express this as: 10^k - 1.

Then the n in 9n can be substituted for 10^k - 1. That will give us 9(10^k - 1).
That is equal to 9(10^k) - 9.
Both of these numbers are divisible by 9 ...

This doesn't seem like the correct way to do this proof. Help?

 

[lev888]

"if and only if" means you need 2 proofs:
1. If n is a multiple of 9, prove that the sum of its digits is a multiple of 9
2. If the sum of digits of n is a multiple of 9, prove that n is a multiple of 9

Couple of points regarding your attempt:
If n is a multiple of 9, then n = 9k (n=9n doesn't make sense)
Why do you think n=10^k - 1 follows? Digits of 36 add up to 9, but it's not 10^k - 1.

 

[Dr.Peterson]

For any positive integer n, n is a multiple of 9 if and only if the sum of the digits of n is a multiple of 9.

Here's what I have so far, but I think I'm making a mistake along the way:

Proof:
There exists a positive integer n that is a multiple of 9 if and only if the sum of the digits of n is a multiple of 9.

"There exists" is inappropriate there; it looks as if you added it just because it looked fancy. Nothing about the statement involves existence of a number n! It is a claim about any number n.

The first step in writing a proof is to be sure you understand what you are trying to prove, and that is the reason we sometimes restate it. But the restatement has to be clearer, while meaning exactly the same thing.

This is not a simple proof, if only because it's hard to state exactly how the sum of the digits of a number relates to the number itself, when it may have any number of digits. So you might start by writing out an expression for n in terms of its digits.

Do you know any modular arithmetic, which might be a useful tool? Have you been given any examples involving the digits of a number? If I were tutoring you face to face, I would be skimming your current chapter to see what you are learning, and get ideas on what approaches you might be expected to try.

 

[Cubist]

I would start by showing that mod(10^p, 9)=1 where p is an integer and p≥0

Can you see how this would help?

 

[Steven G]

Ah you are in algebra.
Here is what I would do at that level.

Fist you have to understand that if a+b is a multiple of 9 and a is also a multiple of 9, then b must also be a multiple of 9.
To see this clearly suppose you have a multiple of 9 marbles (a+b) and you put some (a) of the marbles in your left pocket and the rest (b) of them in your right pocket. Then you keep removing 9 at a time from your left pocket and eventually have none left in that pocket ( since a is a multiple of 9). Since all the marbles, a+b, is a multiple of 9 then it must be true that the marbles in your right pocket is also a multiple of 9.

Let k be any integer. So k = a_n10ⁿ + a_n-110^n-1 + ... + a₁10¹ + a₀10⁰ = a_n(99...9 +1) + a_n-1(999...9 +1) + ... + a₁(9+1) + a₀1

= [a_n(99...9) + a_n-1(999...9) + ... + a₁(9)] + [a_n + a_n-1 + ... + a₁ + a₀]

Can you finish up from here?