Monday, April 9, 2018

Prove that none of the numbers $1_{(9)},11_{(9)},111_{(9)},1111_{(9)}cdots$ are prime




I want to prove that none of the numbers $1_{(9)},11_{(9)},111_{(9)},1111_{(9)}\cdots$ are prime where $x_{(9)}$ means, the number $x$ is in base $9$. My first attempt was to try mathematical induction. $V(0)$ works because $1$ is not a prime. But then i couldn't prove the induction step anyhow.
$$1+9+81+...+9^n \text{ is not prime}\Rightarrow 1+9+81+...+9^{n+1} \text{ is not prime}$$
My next try was to prove it with geometric series.
Let $$s_n=\sum_{k=1}^n9^n$$
We are proving $\forall n\in\Bbb{N}:s_n \text{ is not prime}$.
using the sum of geometric series$$s_n=\frac{9^n-1}{8}$$ But here I am stuck again and have no idea how to show that this can't be prime for any $n\in\Bbb{N}$.


Answer



Hint
$$9^n-1=(3^n)^2-1=(3^n-1)(3^n+1)$$




Now, $3^n-1, 3^n+1$ are two consecutive even numbers, thus one is divisible by $4$ and the other by 2. Consider the two cases (when $4|3^n-1$ and $4|3^n+1$) and write $\frac{9^n-1}{8}$ as a product of two integers. Explain why neither can be 1.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...