Deeper on Divisibility

Number Theory Level 2

True or False?

Every Fibonacci number that is divisible by 31 is also divisible by 61.

True False

2 solutions

Tony Carlson
Oct 1, 2017

It sounded so crazy it had to be true

Efren Medallo
Sep 21, 2017

The Fibonacci sequence is a clear example of a divisibility sequence , which exhibits the property that for any two positive integers $(a,b)$ , if $a| b$ , then $F_a | F_b$ .

Now the smallest Fibonacci number that is divisible by $61$ is $F_{15} = 610$ . In that case then, every $15^{th}$ member of the sequence is divisible by $61$ .

Now consider the smallest Fibonacci number that is divisible by $31$ . By inspection, we find out that it is $F_{30} = 832040$ . This means that every $30^{th}$ member of the sequence is also divisible by $31$ .

As we can observe, every $30^{th}$ member of the sequence is also every other $15^{th}$ member of the sequence! QED.

What you have is "If $15 \mid n$ then $61 \mid F_n$ ".

However, what you really need is: Does there exist an $n$ such that $15 \not \mid n$ but $61 \mid F_n$ ?

IE You want an if and only if statement, but you don't have that as yet (or at least, not stated in your solution).

Calvin Lin Staff - 3 years, 8 months ago

Deeper on Divisibility

2 solutions

0 pending reports