Skip to page content Home     Posts     CV     Contact     People

Two Divisibility Problems

2016 May 9

Here are two interesting problems regarding divisibility that I found interesting.

Prove that $(n-1)^2 \mid n^k-1$ if and only if $(n-1) \mid k$.
Prove that $F_{n} \mid F_{kn}$ for all integer $n$ and $k$, where $F_i$ denotes the ith Fibonacci number.

The first is from Math Stackexchange. By breaking this problem down into a few lemmas, it can be done without too much difficulty.

Lemma #1: The sum $$a^0+a^1+...+a^b$$ is equal to $$\frac{a^{b+1}-1}{a-1}$$

This lemma can be proven easily, since when the two are set equal to each other, we recieve a truth statement: $$\frac{a^{b+1}-1}{a-1}=a^0+a^1+...+a^b$$ $$a^{b+1}-1=(a-1)(a^0+a^1+...+a^b)$$ $$a^{b+1}-1=-a^0+a^1-a^1+a^2-a^2+...+a^b-a^b+a^{b+1}$$ $$a^{b+1}-1=a^{b+1}-a^0$$ $$a^{b+1}-1=a^{b+1}-1$$

And there is our truth statement, so Lemma #1 is proven.

Lemma #2: The quotient $$\frac{a^b}{a-1}$$ is equal to $$a^{b-1}+a^{b-2}+...+a^2+a^1+a^0+\frac{1}{a-1}$$

By Lemma #1, the following is true: $$\frac{a^b-1}{a-1}=a^0+a^1+...+a^{b-1}$$

From this we can algebraically derive Lemma #2. $$\frac{a^{b}-1}{a-1}=a^0+a^1+...+a^{b-1}$$ $$\frac{a^{b}}{a-1}-\frac{1}{a-1}=a^0+a^1+...+a^{b-1}$$ $$\frac{a^{b}}{a-1}=a^0+a^1+...+a^{b-1}+\frac{1}{a-1}$$ $$\frac{a^{b}}{a-1}=a^0+a^1+...+a^{b-1}+\frac{1}{a-1}$$

Which is equivalent to the statement made by Lemma #2, so Lemma #2 is thus proven.

Lemma #3: The quotient $$\frac{a^b+a^{b-1}+...+a^1+a^0}{a-1}$$ is equal to $$a^{b-1}+2a^{b-2}+...+(b-1)a^1+ba^0+\frac{b+1}{a-1}$$

This can be proven by splitting up the quotient into the sum of many quotients: $$\frac{a^b}{a-1}+\frac{a^{b-1}}{a-1}+...+\frac{a^1}{a-1}+\frac{a^0}{a-1}$$

By Lemma #2, we can expand each of these quotients to form $$(a^{b-1}+...+a^0+\frac{1}{a-1})+(a^{b-2}+...+a^0+\frac{1}{a-1})+...+(a^1+a^0+\frac{1}{a-1})+(a^0+\frac{1}{a-1})$$

Notice now that when we combine like terms, there will be $1$ term in the form $a^{b-1}$, $2$ of the form $a^{b-2}$, and so on, and $b-1$ of the form $a^1$, $b$ of the form $a^0$, and $b+1$ of the form $\frac{1}{a-1}$, so the whole thing condenses to $$a^{b-1}+2a^{b-2}+...+(b-1)a^1+ba^0+\frac{b+1}{a-1}$$

Proving Lemma #3.

Now we can prove that $(n-1)^2 \mid n^k-1$ if and only if $(n-1) \mid k$ using our three Lemmas. By Lemma #1, the quotient of $n^k-1$ and $n-1$ is given by the sum $$n^{k-1}+n^{k-2}+...+n^1+n^0$$

meaning that $(n-1)^2 \mid n^k-1$ if and only if $$(n-1) \mid n^{k-1}+n^{k-2}+...+n^1+n^0$$

If that is true, then their quotient will be an integer. By Lemma #3, the quotient is given by the sum $$n^{k-2}+2n^{k-3}+...+(k-2)n^1+(k-1)n^0+\frac{k}{n-1}$$

All terms of this sum must be integers except for the last term, $$\frac{k}{n-1}$$

The entire sum will be an integer if and only if that last term is an integer, and the last term is an integer if and only if $(n-1) \mid k$, proving our initial statement.

The second problem is from a pattern that I noticed whilst playing around with the Fibonacci Sequence. My conjecture was that, if we let $F_n$ denote the nth Fibonacci number (starting with $F_1=F_2=1$), then $F_n \mid F_{kn}$ for positive integer $k$ and $n$. The proof of this statement reuqires only one Lemma before it can be proven using mathematical induction.

Lemma #4: $F_a=F_bF_{a-b+1}+F_{b-1}F_{a-b}$

By the definition of the Fibonacci Sequence, $$F_a=F_{a-1}+F_{a-2}$$

and by substitution, $$F_a=2F_{a-2}+F_{a-3}$$

and $$F_a=3F_{a-3}+2F_{a-4}$$

This pattern necessarily continues on forever, because whenever another substitution happens, one coefficient is shifted and the coefficient of the new term is the sum of those of the coefficients of the previous two. Now Lemma #4 is proven.

Now we are ready to prove the theorem. First we show that it holds for $k=2$. By Lemma #4, $$F_{2n}=F_nF_{n+1}+F_{n-1}F_n$$ $$F_{2n}=F_n(F_{n+1}+F_{n-1})$$

This shows that $F_n \mid F_{2n}$.

Now suppose that, for some $k$, my conjecture is true, so that $F_n \mid F_{kn}$. Then, by Lemma #4, by letting $a=(k+1)n$ and $b=kn$, $$F_{(k+1)n}=F_{kn}F_{n+1}+F_{kn-1}F_n$$

Now, since we assumed that $F_n \mid F_{kn}$, we can say that $F_{kn}=c*F_n$ for some integer $c$, and by substitution, $$F_{(k+1)n}=c*F_nF_{n+1}+F_{kn-1}F_n$$

We can now factor out $F_n$: $$F_{(k+1)n}=F_n(cF_{n+1}+F_{kn-1})$$

Showing that if $F_{kn}$ is divisible by $F_n$, so is $F_{(k+1)n}$. However, since we have already proven that $F_n \mid F_{2n}$, we know the statement must be true for all positive integral $k$, thus proving that $F_n \mid F_{kn}$ for all positive integral $k$ and $n$.