# Homework Help: Direct Proof

1. Jan 17, 2010

### Dollydaggerxo

1. The problem statement, all variables and given/known data
Prove that 10^n leaves remainder 1 after dividing by 9.

3. The attempt at a solution

There is an integer K, such that 10^n = 9k + 1

Where do i go from here if I want to do it just directly?

2. Jan 17, 2010

### rasmhop

Do you know modular arithmetic?
$$10^n \equiv 1^n =1 \pmod 9$$
Alternatively use the binomial theorem by writing:
$$(9+1)^n = \sum_{i=0}^n \binom{n}{i} 9^i = 1 + 9\sum_{i=1}^n \binom{n}{i}9^{i-1}$$
Finally you could use induction by noting that if $10^n = 9k+1$, then,
$$10^{n+1} = 10^n 10 = (9k+1)(9+1) = 9^2k + 9k + 9 + 1$$
I would call all approaches direct though induction may not qualify depending on your definition.