Inductive Proof for Divisibilty of Elements of a Set

Question

I have the following question: "Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be defined $\forall n\in\mathbb{N}$, by $f(n)=10^{9+16n}-7$, let $A=\{m\in\mathbb{N}|m$ is divisible by $11\}$, $B=\{m\in\mathbb{N}|m$ is divisible by $17\}$ and $C=\{m\in\mathbb{N}|m$ is divisible by $137\}$. Give a proof by mathematical induction for the following proposition: $$(f(\mathbb{N})\subseteq B)\wedge(f^{-1}(A\cup C)=\emptyset)."$$ I have been given that $10^{16}-1$ will be useful sometime during the proof as a hint, but I'm not quite sure how to get there. I've tried multiplying my function by $10^{16}$, but I'm then just left with $$10^{9+16(n+1)}-7\cdot10^{16}.$$ I'm not quite sure what to do from there. Help would be much appreciated.

Answer 1

First part. Let prove $f(n) \subset B$ $\forall n \geq 0$. For $n=0$ is true. The inductive hypothesis is $$ 10^{9+16n}-7 = 0 \mod 17 \Leftrightarrow 10^{9+16(n+1)}= 7 \mod 17 $$ so $$ 10^{9+16(n+1)}-7 = 10^{9+16n}10^{16}-7 =7\cdot10^{16}-7=0\mod 17 $$ For the last equality I use again WolframAlpha. So $f(\mathbb{N})\subset B$.

Second part. For $n=0$, we have $11,137 \not\mid f(0)$. The inductive hypothesis is $11,137\not\mid f(k)$ $\forall k \leq n$. Let's see for $n+1$. By reductio ad absurdum, suppose $11$ or $137\mid f(n+1) $.

• Suppose $11 \mid f(n+1)$. Remember $11\not \mid f(n)$ and $10^{16} = 1 \mod 11$. $$ 10^{9+16(n+1)}-7 = 10^{9+16n}10^{16} - 7 = 10^{9+16n}-7 = f(n) = 0\mod 11 $$ wich is a contradiction.
• Suppose $137 \mid f(n+1)$. Remember $137\not \mid f(n)$ and $10^{16} = 1 \mod 137$. $$ 10^{9+16(n+1)}-7 = 10^{9+16n}10^{16} - 7 = 10^{9+16n}-7 = f(n) = 0\mod 137 $$

Edit: An alternative proof to the first part. You know that $$ a = b \mod \phi(c) \Rightarrow d^a = d^b \mod c $$ Since $\phi(17)=16$, $$ 10^{9+16n}-7 = 10^9-7 = 0 \mod 17$$ For the last equality I used WolframAlpha.

Answer 2

The hint is that $10^{16}\equiv 1 \mod 17$ by Fermats Little Theorem.

That $10^{16} \equiv (-1)^{16} \equiv 1 \mod 11$

And that $10^{16} \equiv 1 \mod 137$ which I figured by .... well, a calculator. $137$ is prime and $137-1 = 136 = 8*17$ so $10^8$ is likely to be equiv $1$. And indeed $10001 = 137*37$ (oh, yeah... one of those weird one,three, seven numbers... $37*3 = 111$ and so on.....)

This means that by induction:

$10^{9 + 16(n+1)} -7 = 10^{9 + 16n}*10^{16} -7 \equiv 10^{9 + 16n} - 7\mod 17,11,137$ so by induction:

$10^{9+16n} - 7\equiv 10^9 - 7 \mod 17,11,137$

(Actually we don't need induction for that. Just $10^{9+16n}-7\equiv 10^9*(10^{16})^n - 7\equiv 10^9 - 7 \mod 17,11,137$.

So we just have to prove.

$10^9 - 7 \equiv 0\mod 17$

$10^9 -7 \not\equiv 0 \mod 11$

and $10^9 - 7\not\equiv 0 \mod 137$

Let's see. $10^{16}\equiv 1 \mod 17$ so $10^8 \equiv \pm 1 \mod 17$. If it's equiv $-1$ than we have $10^9-7\equiv -10-7=17\equiv 0 \mod 17$ and that'd be nice. $17*3 = 51$, $17*6 =102$ so $10^2\equiv -2 \mod 17$ so $10^{8}\equiv (-2)^4\equiv 16\equiv -1 \mod 17$. Good.

$10^9 -7 \equiv (-1)^9-7\equiv -8 \mod 11$. So that's that.

So mod $137$. Well, $1001 = 137*73$ so $10^4 \equiv -1 \mod 137$ so $10^9-7\equiv (-1)^2*10 -7 = 3\mod 137$.