Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post.

This problem is from assignment 6. The notes from this lecture can be found here.

Prove that every integer $a$ is congruent to the sum of its decimal digits modulo 9.

Let $s$ be an $(n+1)$-digit integer given by $s=a_n\cdot10^n+\dots+a_2\cdot10^2+a_1\cdot10^1+a_0\cdot10^0$ with $a_i\in\mathbb{Z}$ such that $0\leq a_i\leq9$. Then
$ \begin{align} s\,\mathrm{mod}\,9&=\bar{s}\\ &=\overline{a_n\cdot10^n+\cdots+a_2\cdot10^2+a_1\cdot10^1+a_0\cdot10^0}\\ &=\overline{a_n\cdot10^n}+\overline{\cdots}+\overline{a_2\cdot10^2}+\overline{a_1\cdot10^1}+\overline{a_0\cdot10^0}\\ &=\overline{\overline{a_n}\cdot\overline{10^n}}+\overline{\cdots}+\overline{\overline{a_2}\cdot\overline{10^2}}+\overline{\overline{a_1}\cdot\overline{10^1}}+\overline{\overline{a_0}\cdot\overline{10^0}}\\ &=\overline{\overline{a_n}\cdot1}+\overline{\cdots}+\overline{\overline{a_2}\cdot1}+\overline{\overline{a_1}\cdot1}+\overline{\overline{a_0}\cdot1}\\ &=\overline{a_n}+\overline{\cdots}+\overline{a_2}+\overline{a_1}+\overline{a_0}\\ &=a_n\,\mathrm{mod}\,9+\cdots+a_2\,\mathrm{mod}\,9+a_1\,\mathrm{mod}\,9+a_0\,\mathrm{mod}\,9 \end{align} $

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

share|improve this question
3  
Reasoning is sound, although you should point out somewhere that $\overline{10^n}=\overline{10}^n=\overline{1}^n=\overline{1}$. Also, it looks weird to have $\overline{\cdots}$, just $\cdots$ suffices. And if you aren't going to distinguish between the regular + and its modular version then you need to carry that really long \overline through until the last line. –  Alex Becker Jan 17 '12 at 0:45
    
I second @AlexBecker's comments. –  user21436 Jan 17 '12 at 0:52
add comment

4 Answers

up vote 4 down vote accepted

Your suggestion works if you are satisfied $\overline{a_n\cdot10^n} \equiv \overline{\overline{a_n}\cdot\overline{10^n}} \equiv \overline{\overline{a_n}\cdot1} \equiv \overline{a_n} \mod 9$, which is indeed true.

Another way is

$$\begin{align} s&={a_n\cdot10^n+\cdots+a_2\cdot10^2+a_1\cdot10^1+a_0\cdot10^0}\\ &={a_n\cdot 99\ldots99+\cdots+a_2\cdot 99+a_1\cdot 9 +a_0\cdot 0 }+\sum_{i=0}^n a_i\\ &=9({a_n\cdot 11\ldots11+\cdots+a_2\cdot 11+a_1\cdot 1 +a_0\cdot 0 )}+\sum_{i=0}^n a_i \end{align}$$

so $s \equiv \sum_{i=0}^n a_i \mod 9.$

share|improve this answer
add comment

Just another way.

Clearly $9\vert (10-1)$. Suppose that $9\vert (10^n - 1)$, $n\gt 1$. Then $$10^{n+1}-1 =10\cdot 10^{n}-1=9\cdot 10^n + (10^n - 1)$$ thus $9\vert (10^{n+1}-1)$. Therefore $9\vert (10^n-1)$ for any $n\in\mathbb{N}$.

Now take an integer $$a=\sum_{i=0}^n a_i10^{i},$$ where $a_i\in \{0,1,\ldots,9\}$. Then $$a-\sum_{i=0}^na_i=\sum_{i=0}^n a_i10^{i}-\sum_{i=0}^na_i=\sum_{i=1}^n a_i(10^{i}-1),$$ therefore, by the established above $$a\equiv \sum_{i=0}^na_i \pmod 9$$

share|improve this answer
add comment

HINT $\rm\ mod\ 9\!:\ 10\:\equiv\: 1\ \Rightarrow\ f(10)\:\equiv\: f(1)\ $ for all polynomials $\rm\:f(x)\:$ with integer coefficients.

The above applies to radix notation since it clearly has polynomial form in the radix.

Alternatively put $\rm\ x\: =\: 10\ $ in $\rm\ x-1\ |\ f(x)-f(1)\ $ by the Factor Theorem.

share|improve this answer
    
@Downvoter If something is not clear then please feel free to ask questions and I'll happily elaborate. –  Bill Dubuque May 19 '12 at 1:41
add comment

I write this answer in keeping with my comment:

You need to prove that $\overline {ab}=\overline{\bar a\bar b}$. There are many ways of looking at this, for instance see, Benjamin Lim's answer, here. I shall write a number theoretic proof here:

Suppose $\bar k$ denotes the remainder obtained when $k$ is divided by$q$, we have, $a=b_1q+\bar a; b=b_2q+\bar b$ . So, you have $$ab=(b_1b_2q+b_1\bar b+b_2\bar a)q+\bar a \bar b$$ and this proves that, $\overline{ab}=\overline{\bar a \bar b}$.

Further, on the same line, you'll need to prove for the sum and the fact that $10^n \cong 1 (mod~~9)$

There are very minor gaps which you can still fill as a beginner, as others have pointed out.

Sorry for the late edits!!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.