If the gcd(s, t)=1, prove $F_s F_t$ divides $F_{st}$ for all s,t > 1      $F_n$ is the Fibonacci sequence, such that $$F_n = F_{n-1} + F_{n-2}$$   I know that it needs to be shown that $F_s F_t\mid F_{st}$ which has the implication that $F_{st} = F_s F_tk$.   I considered that it may be useful to use the theorem that states: the gcd of two fibonacci numbers is also a Fibonacci number with the form $\gcd(F_s,F_t)= g$ where $g= \gcd(s,t)$ or a Corollary relating to this theorem. But I cannot see how this directly applies to the problem.   Is it valid to say that because a theorem states for any $s&gt;1, t&gt;1$, $F_{st}$ is divisible by $F_s$ then that is an implication for $F_s F_t\mid F_{st}$ because the $\gcd(s,t) =1$?
26109
Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which will cover the all my results below:   Every third Fibonacci number is even. 3 divides every 4th Fibonacci number. 5 divides every 5th Fibonacci number. 4 divides every 6th Fibonacci number. 13 divides every 7th Fibonacci number. 7 divides every 8th Fibonacci number. 17 divides every 9th Fibonacci number. 11 divides every 10th Fibonacci number. 6, 9, 12 and 16 divides every 12th Fibonacci number. 29 divides every 14th Fibonacci number. 10 and 61 divides every 15th Fibonacci number. 15 divides every 20th Fibonacci number.
23402
(a) Prove $(k,n+k)=1$ iff $(k,n)=1$. (b) Is it true that $(k,n+k)=d$ iff $(k,n)=d$? (all variables are integers, (a,b) means gcd(a,b))  For (a), I can only get so far.  $(k,n+k)=1\ \Rightarrow\ kq_1+(n+k)q_2=k(q_1+q_2)+nq_2=1$.  Note that we don't yet have that theorem (from a different class) that says something like if $d=(a,b)$, then $d$ is the smallest (or is it biggest) number which can be made by $ak_1+bk_2$, (which I'm not quite sure how it would help, anyway). So I'm stuck.
18057
The proof is already given in the textbook but I tried other way around.   Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,a)=1$ and $\gcd(p,b)=1$. Given that we can construct linear combinations   $sp+ta=1$ together with $up+wb=1$. Multiplying the left and the right sides of the equations we get  $spup+spwb+taup+tawb=1$ or $p(sup+swb+tau)+ab(tw)=1 \implies \gcd(p,ab)=1$. This is a contradiction.   Is it rigorous and sound proof?
41678
As stated in the title, the problem to prove is  Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$.  I think I've proved it, but I would like a second opinion. Here goes:  PROOF Suppose $\exists d \neq 1 \in \mathbb{Z}$ s.t $\gcd(ab,c)=d$. It follows then that $d|ab$ and $d|c$. Now, if $d|a$ but not $b$, then since $d|c$, by linearity we have $d|\gcd(a,c)$. But $\gcd(a,c)=1$ so then $d=1$. The argument for $d|b$ is similar, resulting in $d=1$. Thus, since both cases lead us to $d=1$, we have a contradiction on our hands $\implies$ $ab$ and $c$ must be relatively prime $\implies \gcd(ab,c)=1$. $Q.E.D$  The question: was this a valid argument or do you think I should provide more?
3339
If $F_n$ is the $n$-th fibonacci number, then prove that, $$F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$$  I tried the idea of using Pascal's triangle, but it seems to need some adjustment, so I am stuck, please help.    Any combinatorial argument would be of greater help than rigorous proof.  Thank you.
58390
The following problem:  The Fibonacci number is denoted by  $f_{n}$, show that the following holds when $n$ is a positive integer:  $f_{0}f_{1}+f_{1}f_{2}+...+f_{2n-1}f_{2n} = f^{2}_{2n}$  My idea was to do an induction proof, which holds for $n$ = 1  $f_{0}f_{1} + f_{1}f_{2} = f^{2}_{2}$  So we assume it holds for $n$ and show for $n+1$  $f_{0}f_{1}+f_{1}f_{2}+...+f_{2n-1}f_{2n} + f_{2n}f_{2n+1} = f^{2}_{2n} + f_{2n}f_{2n+1}$  I fail to get  $f^{2}_{2n+1}$ out of the term  $f^{2}_{2n} + f_{2n}f_{2n+1}$  Is there a difference between "show that" and "prove that". So might be induction the wrong tool here?  Many thanks for your hints in advance :-)
35358
Say we have two integers $n$ and $k$, such that $0 &lt; k &lt; n$ and $gcd(n, k) = 1$.  Why is it that if we take every integer $x\in\{0,\dots, n-1\}$ and compute $k\cdot x \ (mod \ n)$, we get as remainders all numbers from $0$ to $n-1$, with no repeats?  In other words, why is $\ f:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$, $\ f(x)=k\cdot x\ (mod\ n)$ a bijection for $k,n\in\mathbb{N},\ gcd(k,n)=1$?
94204
As stated in the tag, I'm trying to prove by induction the claim $F_{2n} = F^2_{n+1} - F^2_{n-1}$, where $F_{n}$ is the $n^{th}$ Fibonacci number. I've spent hours on the inductive step without substantial progress, and am hoping someone can provide a path to the desired result.    To facilitate the proof, we're given $F_{2n-1} = F^2_{n} + F^2_{n-1}$  (Also, in various past attempts not reflected here I tried to use the following substitutions whenever it seemed prudent: $F_{n} = F_{n-1} + F_{n-2} = F_{n+1} - F_{n-1}$; and $(x^{2} - y^{2}) = (x - y)(x + y)$).  For the inductive step, let $n\geq 1$ and assume $F_{2n} = F^2_{n+1} - F^2_{n-1}$. For $n+1$ we want to show $F_{2(n+1)} = F^2_{n+2} - F^2_{n}$. So  \begin{align}   F_{2(n+1)} &amp;= F_{2n + 2} \\              &amp;= F_{2n+1} + F_{2n} \\              &amp;= (F_{2n} + F_{2n-1}) + F_{2n} \\              &amp;= 2 F_{2n} + F_{2n - 1} \\              &amp;= 2 (F^2_{n+1} - F^2_{n-1})                   + F^2_{n} + F^2_{n-1}                       &amp;&amp;\text{by the inductive hypothesis} \tag{1} \\              &amp;=...F^2_{n+2} - F^2_{n}                      \end{align} I have two challenges.  The first is squeezing $-2 F^2_{n}$ out of (1).  The only reasonable way I can see to do that is to expand the $-F^2_{n-1}$ term in  $2 F^2_{n+1} - F^2_{n-1}$ to $-(F_{n} - F_{n-2})^2$. If in instead I combine it with $F^2_{n-1}$ then it seems impossible to generate the $-2 F^2_{n}$ term needed to offset $F^2_{n}$ and produce $-F^2_{n}$.   The second challenge is to find $(F^2_{n+2}$ in (1), and the only way I can see to do that is to expand the $F^2_{n+1}$ term in $2(F^2_{n+1} - F^2_{n-1})$to $(F_{n+2} - F_{n})^2$. Doing that not only generates $2 F^2_{n}$ which totally screws things up, but it also generates a bunch of intermediate terms I can't get rid of, and it's driving me crazy.
40178
Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$. My attempt is let $\gcd(ab,c)=d$. Since $d \mid ab$ and $d \mid c$ , $d \mid (abt+cs)$ for some integers $s$ and $t$. Then by definition of divisibility, we have $$abt+cs=dk$$ for some integers $k$. Then I got stuck here.
59250
I have a bit difficulty to proofe that two consecutive numbers are coprime. I have the following  The property $P(n)$ is the equation $(F_{n+1},F_n)=1$ where F_i the sequence of fibonacci is and $n \in \mathbb {N}$.  Induction hypothesis: $gcd(F_{n+1},F_n)=1$  $P(0)$ is true because $F_1=1, F_0=1$ and $gcd(1,1)=1$  To show: $gcd(F_{n+2},F_{n+1})=1$  Proof:  Fibonacci formula says  $F_{n+2}=F_{n+1}+F_n$  This is as faar as I got. How can I now get to $gcd(F_{n+2},F_{n+1})=gcd(F_{n+1},F_n)$ which would then proofe it?
63246
By calculating for $n\in \{1,2,3,4,5,6,7\}$, I've formulated the rule  \begin{equation} F_{n+1} \cdot F_{n-1} = F_n^2 + (-1)^n, \end{equation}  where $F_n$ is the $n$th fibonacci number. I want to show that this is true for all $n \in \mathbb{N}$.   I tried using induction, with $n=1$ as the basis step, but didn't get very far:  For the induction step, we assume the formula holds for a $n = k$, and checks for $n=k+1$: \begin{align*} F_{k} \cdot F_{k+2} &amp;= F_{k} \cdot (F_{k+1} + F_{k})  \\ &amp;= F_k \cdot F_{k+1} + F_k^2 \\ \end{align*} If somehow $F_k \cdot F_{k+1} = (-1)^k$, then I would be done. But I don't see how that's possible.   Is there a better way of proving this, maybe without using induction? Or am I just going about it the wrong way?
94023
I need your help with this: Let $f$, $p$, and $g$ be a polynomials in $F[x]$, assume that $f$, $g$, and $p$ are nononzero.  If $\gcd(f,p)=1$ and $fg$ is divisible by $p$ with no remainder, I need to prove that $g$ is  divisible by $p$ with no remainder  Thanks.
47520
While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it.     Show that if the Fibonacci sequence has a term divisible by a natural number $m$, then there are infinitely many such terms.
62634
Let $F_n$ be the Fibonacci sequence where  $F_0$ = 0  , $F_1$ = 1 and  $F_n$ = $F_{n-1}$ + $F_{n-2}$.                   I want to prove the following by induction. $$\sum_{k=1}^{n}F_k = F_{n+2}-1$$ Here is what I have so far.  Can anybody tell me if I am right?  Base case = n=1  $F_k$ = 1 = LHS  $F_{1+2}$ - 1 = 2 - 1 = 1 = RHS  Statement is true for n=1.  Assume statement is true for n=i.  $$\sum_{k=1}^{i}F_k = F_{i+2}-1$$  Prove statement is true for n=i+1.  $$\sum_{k=1}^{i+1}F_{k} = F_{((i+1)+2)}-1$$  $F_1$ + $F_2$ +...+ $F_i$ + $F_{i+1}$ = $F_{((i+1)+2)}-1$  $F_{i+2}$ - 1 + $F_{i+1}$ = $F_{((i+1)+2)}-1$  $F_{((i+1)+2)}-1$ = $F_{((i+1)+2)}-1$  Statement holds for n=i+1
55152
Given the Fibonacci sequence $(F_1, F_2,F_3, ...)$ how do I prove that if $m|n$ then $F_m|F_n$? Can this be proven with mathematical induction?
13690
Suppose that $m,n \in \mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d \in \mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(\frac{m}{c},\frac{n}{d}) = 1$.   Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?
53762
The definition of a Fibonacci number is as follows:  $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$   Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. $$F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$$  I am pretty sure I should use weak induction to solve this. My professor got me used to solving it in the following format, which I would like to use because it help me map everything out...  This is what I have so far:  Base Case: Solve for $F_0$ and $F_1$ for the following function: $F_nF_{n+1}$.  Inductive Hypothesis:  What I need to show: I need to show $F_{n+1}F_{n+1+1}$ will satisfy the given property. Proof Proper:  (didn't get to it yet)  Any intro. tips and pointers?