Proving that a number is divisible by 3 if and only if the sum of its digits is divisible by 3 I am currently taking a sets and numbers module at uni and wanted to get better at writing proofs. I would appreciate any feedback on how to improve my proof below.
For this proof we know that $9|(10^n-1)$ for all $n\in\mathbb{N}$
Suppose $f(n)$ is a number with $n$ digits $$f(n)=k_010^0+k_110^1+\cdots+k_{n-1}10^{n-1},\;\;\forall k\in\mathbb{N}$$Let $f^\prime(n)$ be the sum of $f(n)$'s digits $$f^\prime(n)=k_0+k_1+\dots+k_{n-1},\;\;\forall k\in\mathbb{N}$$We can see that $$f^\prime(n)=(k_010^0+k_110^1+\cdots+k_{n-1}10^{n-1})-(k_1(10^1-1)+k_1(10^2-1)+\cdots+k_{n-1}(10^{n-1}-1))$$We know that every term in $k_1(10^1-1)+k_1(10^2-1)+\cdots+k_{n-1}(10^{n-1}-1)$ is divisble by $9$ thus the entire sum is divisble by $9$. Let the sum be denoted by $v$. We can also see that $k_010^0+k_110^1+\cdots+k_{n-1}10^{n-1}$ is just $f(n)$. Therefore,$$f^\prime(n)=f(n)-v$$so$$f(n)-f^\prime(n)=v$$Now because v is divisible by $9$ we have that $f(n)-f^\prime(n)$ is also divisible by $9$ so $$\frac{f(n)-f^\prime(n)}{9}=q,\;\;\forall q\in\mathbb{N}$$which means that$$\frac{f(n)}{9}-\frac{f^\prime(n)}{9}=q$$Thus both $9|f(n)$ and $9|f^\prime(n)$. We have then proven that $f(n)$ is divisible $9$ iff $f^\prime(n)$ is divisible by $9$. By the transitivity of divisibility we then have that both $3|f(n)$ and $3|f^\prime(n)$. Therefore $f(n)$ is divisible by $3$ if and only if $f^\prime(n)$ is divisible by $3$. End of proof.
 A: Looks mostly good to me. The core idea is excellent.
A couple of aesthetic concerns. For instance, you don't need any reference to $n$ in $f(n)$. It is enough to say

Let $f = k_0 + \cdots + k_{n-1}\cdot 10^{n-1}$ be an $n$-digit number, and $f' = k_0+\cdots + k_{n-1}$ be the sum of its digits.

Also, perhaps more importantly, I think you should stop once you reach $f'=f-v$. At that point, you know $v$ is divisible by $9$ (and therefore $3$), so it is almost an immediate consequence that $f$ is divisible by $9$ (or $3$) exactly when $f'$ is.
A: 
Suppose $f(n)$ is a number with n digits

I think it'd be better to specify what kind of number and not simply say digits but specify the precise mathematical thing you're using - so e.g. "Let $f(n) \in \Bbb N$ be a natural number with decimal expansion $f(n) = k_0 10^0 + k_1 10^1 + ... + k_n 10^n$. Furthermore I think your $f(n), f'(n)$ notation is extremely unfortunate since it clashes quite heavily with the common notation for functions and derivatives and there's no clear functional relationship here and it focuses the attention on the $n$ which isn't that important. So maybe make it $r \in \Bbb N$ and call the sum $\bar{r}, s, \sigma$ or something like that.
You should also pay attention to properly terminate your sentences with a full-stop, even if they end in symbols. It is also not very common to write something like "End of proof."; either omit this bit completely or include it into the flow of the text "By the transitivity of divisibility we then have that both $3|f(n)$ and $3|f′(n)$, which completes our proof that $f(n)$ is divisible by $3$ if and only if $f′(n)$ is divisible by $3$.".
As for the proof itself: if you're familiar with modular arithmetic you can try applying it to this theorem with great success - it'll trivialize the result.
A: Good effort!
I'm afraid I don't agree with the part where you say "$\tfrac 19 (f(n) - f'(n)) = q, \forall q \in \Bbb N$"! I think that was probably a typo, and you meant to convey "for some $q \in \Bbb N$", which you would write with the symbol "$\exists$", rather than "$\forall$" (or, even better, just in words).
Similarly, earlier on you end some equalities with a bit of a random "$\forall k \in \Bbb N$". This doesn't belong here, as you don't even have a $k$ in the equation, and you're not claiming that the equation holds for all natural numbers! Whenever you write $\forall k, \dots$, you should make sure that what you've written makes sense if you replace the symbols "$\forall k$" with the words "for all $k$".
Your last paragraph also seems a bit dodgy to me. As you've written it, it's not necessarily true that "$9 \mid f(n)$ and $9 \mid f'(n)$", and that's not what you're trying to show (though it would have been sufficient if it was true)! Remember your $f(n)$ was an arbitrary natural number, and for instance $9 \nmid 1$. If your reasoning was along the lines of "we divided some stuff by $9$ and ended up with an integer, so the stuff we were dividing must have been cleanly divisible by $9$", then this is wrong, for example as we can have things like $\tfrac 19 - \tfrac 19 = 0$, or $\tfrac{10}9 - \tfrac 19 = 1$, etc.
This also means that your deduction that $3 \mid f(n)$ and $3 \mid f'(n)$ is not true.
What you do have to show is actually two things.

*

*First, you should assume that $9 \mid f(n)$ (and make it very explicit in your proof that you are assuming this), and use this to prove that $9 \mid f'(n)$.

*Next, you should undo the assumption that $9 \mid f(n)$, and now instead assume that $9 \mid f'(n)$, and use this to prove that $9 \mid f(n)$.

This would finish your proof. As Arthur says, the nicest way to do this is to use the fact that the difference is divisible by $9$. However, you can still do this by using your later equation showing that $f(n) / 9 - f'(n) / 9$ is an integer, and the fact that $a/b$ is an integer if and only if $b \mid a$. Here the reasoning would go:

*

*Suppose $9 \mid f(n)$. Then $f(n) / 9$ is an integer, so $f(n) / 9 - [f(n) / 9 - f'(n) / 9]$ is an integer, as both of these are integers. This just says $f'(n) / 9$ is an integer, ie $9 \mid f'(n)$.

*Conversely, suppose instead that $9 \mid f'(n)$. Then $f'(n) / 9$ is an integer, so $f'(n) / 9 + [f(n) / 9 - f'(n) / 9]$ is an integer, which just says $f(n) / 9$ is an integer, ie $9 \mid f(n)$.

Therefore $9 \mid f(n) \iff 9 \mid f'(n)$. QED.
To deduce from your proof that $3 \mid f(n) \iff 3 \mid f'(n)$, you can note that since $f(n) - f'(n)$ is a multiple of $9$, it's also a multiple of $3$, so from that point on you can use the same proof again but just for $3$. In fact, what we could really extend the proof to show is indeed that in general, if $n \mid a - b$, then $n \mid a \iff n \mid b$, which is kind of what some of the other answers are getting at.
I agree that your $f(n)$ notation is a little confusing. I personally also try to avoid using the letters $q$ or $v$ for arbitrary natural numbers until I have at least exhausted $n$, $m$, $k$, $l$, $a$, $b$, $c$ (since $q$ is a good letter for either a rational number or a prime number, and $v$ is a good letter for a vector or a velocity). I would recommend structuring your proof a little like this:
Let $n \in \Bbb N$, and let $k = k_0 + 10k_1 + \dotsb + 10^n k_n \in \Bbb N$ be an arbitary $n$-digit natural number, with each $k_i \in \Bbb N$. Write $s = k_0 + k_1 + \dotsb + k_n$ for the digital sum.
Then (because of some algebra), $9 \mid k - s$. Particularly, we can write $k - s = 9m$ for some integer $m$.
So suppose that $9 \mid k$, ie we can write $k = 9a$ for some integer $a$. Then $s = k - (k - s) = 9(a - m)$, so indeed $9 \mid s$.
Conversely, suppose instead that $9 \mid s$. Write $s = 9b$ for some integer $b$. Then $k = s + (k - s) = 9(b + m)$, so indeed $9 \mid k$.
Hence $9 \mid k \iff 9 \mid s$. QED. (and if all you wanted to prove was that $3 \mid k \iff 3 \mid s$, then literally just replace all the $9$s with $3$s).
Note that I didn't need to use any quantifiers (symbols like $\forall$ or $\exists$) at all! Quantifiers are great, but don't overuse them. Writing things in words is almost always a good idea.
I hope that you found some part of that helpful. Again I should say that when you're just starting, proof writing can be very confusing and your proof shows good promise!
