The first question was to prove that $\gcd(F_{n+1},F_n) = 1$ So i tried to use it but with no success. any help or clue will appreciated thanks
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?
24558
How to show that     $$ \gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b ) $$    $a,b\in \mathbb Z$   where $d=\gcd(a,b)$?    Note $\ $ Some of the answers below were merged from . The answers (and their comments) may depend on context provided in that question.
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?
48672
Suppose $a, b \in \mathbb{Z}$, $a &gt; b$, and $\gcd (a,b) = 1$.  What can be said about $\gcd (a+b,a-b)$?  Is it true in general that $\gcd (a+b,a-b) \leq 2$?
27965
Let $a$ and $b$ be two integers. Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$.   This is what I have done so far:  Let $d = \gcd(a,b)$. Then $d=ax+by$ for some $x,y$. Then $d^2 =(ax+by)^2 = a^2x^2 + 2axby+b^2y^2$.  I am trying to create a linear combination of $a^2$ and $b^2$ but do not know what to do with the middle term.  EDIT: I would be interested in seeing a proof using the Fundamental Theorem of Arithmetic as well. I simply thought it would be easiest to use Bezout's Identity.
4209
How to prove $\gcd(a^2, b^2) = (\gcd(a, b))^2$?  My attempt:  Let $\gcd(a, b) = d$.  Then $d|a$ and $d|b$ then $d^2|a^2$ and $d^2|b^2$. i.e $d^2$ divides $a^2 ~~\&amp;~~ b^2$.
103058
Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r).  I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = pcommon b-a = pcommon*(pb-pa)  So: gcd(a, b-a) = common again But I need help for part b guys I can solve it but I need a mathematical expression.
122284
Let $a,m,n\in\mathbf{N}$. Show that if $\gcd(m,n)=1$, then $\gcd(a,mn)=\gcd(a,m)\cdot\gcd(a,n)$.  Proof:  Let $u,v\in\mathbf{Z}$ such that $\gcd(m,n)=um+vn=1$. Let $b,c\in\mathbf{Z}$ such that $\gcd(m,a)=ab+cm$. Let $d,e\in\mathbf{Z}$ such that $\gcd(a,n)=ad+en$.  So $\gcd(a,m)\cdot\gcd(a,n)=a^2bd+cmen+aben+emad$.  Where do I go from here?
119953
I am having trouble proving the two following questions:    If $p|N$, $q|N$ and gcd(p,q)=1, then prove that $pq|N$ If $x$ is non zero positive integer number, then prove that $3|x$ if and only if 3 divides the sum of all digits of $x$.   For both questions I tried to use theorems of discrete mathematics, but I could not find the way to solve them.
32747
Possible Duplicate:        $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1. How can we prove that  $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ z - 1 ,\dots)= b ^ {\gcd (x, y, z, \dots)} - 1\ ? $$
116578
Let $k$ be an integer. Show that   $$\gcd(3k+2,5k+3)=1$$   I know that I can use the Euclidean algorithm, but the $k$ is bugging me. Should I use induction or something?
47293
How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. Thanks for your help!
110473
Let $g_n= {2^2}^n +1 $. Prove $g_0 · g_1 · · · g_{n−1} = g_{n} − 2$.    I'm not sure how to start this proof, if it should be done algebraically or if I should try to use a proof by induction.
55143
The problem's quite clear. Prove that $$\gcd(a^2, b^2) = \gcd(a, b)^2$$  This is easy to understand intuitively and using the Fundamental Theorem of Arithmetic would be easy but I want to prove it by using the Divisibility axioms and the GCD. I have attempted it and am mentioning my results.  Here $d = \gcd(a, b)$.   $$d | ax + by \implies d^2 | a^2x^2 + 2axby + b^2y^2 \implies d^2 | a^2x^2 + b^2y^2 \implies \gcd(a^2, b^2) | d^2$$  I feel that this is not necessary. Please help.  Also, the proof can be generalized to $$\gcd(a^n, b^n) = \gcd(a, b)^n$$  Any help would be appreciated.
87995
If $\gcd(m,n) =1, $ then $m\mathbb{Z}/ mn\mathbb{Z} \cong \mathbb{Z}/(n)$.   Here is my proof to the a/m problem. But I did not make use of $\gcd(m,n) =1.$ Could anyone hence point out and explain the mistakes in my proof? Thank you.   $\text{Define}\ \phi: m\mathbb{Z}/ mn\mathbb{Z} \to \mathbb{Z}/(n)$ by $\phi(ms + mn\mathbb{Z})= [s']_n, \text{where}  \ s \in [s']_n \ \text{and} \ s' \in \{0,...,n-1\}$  $\phi$ is well-defined:  $mx + mn\mathbb{Z} = my + mn\mathbb{Z}$  $\implies mx = my + mr,$ for some $r\in \mathbb{Z}$  $\implies n | x-y$  $\implies [x]_n = [x']_n= \phi(mx + mn\mathbb{Z}) = [y]_n = [y']_n= \phi(my+ mn\mathbb{Z})$  $\phi$ is injective:  It suffices to prove that $\ker(\phi) =\{mn\mathbb{Z}\}.$  Since $\phi(0+mn\mathbb{Z}) = [0]_n, \ker(\phi) \neq \emptyset.$ Given $x = ms+mn\mathbb{Z} \in \ker(\phi),\ $ $ \phi(x)= [s]_n = [0]_n$ $\text{hence}\  s = nk,  \text{for some}\  k \in \mathbb{Z}.$  Clearly, $mnk + mn\mathbb{Z}\subseteq mn\mathbb{Z}.$ Given $y \in mn\mathbb{Z},$ let $y = mnk + (mnc -mnk),$ for some $c \in \mathbb{Z}.$ Then $y \in mnk + mn\mathbb{Z},$ i.e. $mnk + mn\mathbb{Z} = mn\mathbb{Z} $ and hence $\ker(\phi) =\{mn\mathbb{Z}\}.$  $\phi$ is homomorphism:  Let $a = ms + mn\mathbb{Z}, a' = ms'+ mn\mathbb{Z} \in m\mathbb{Z}/mn\mathbb{Z}. $ Then, $\phi(a+a')= \phi(m(s+s') + mn\mathbb{Z}) $  $\exists r \in \{1,...,n-1\}$ such that $[r]_n = [s+s']_n$ and so $\phi(m(s+s') + mn\mathbb{Z}) = \phi(mr + mn\mathbb{Z}) = [r]_n = \phi(a) +_n \phi(a').$   $\phi$ is surjective:  $\text{Given} \ [r]_n \in \mathbb{Z}/(n),\  \text{let}  \ x= mr + mn\mathbb{Z}. \ \text{Then}   \ \phi(x) =[r]_n$
33423
I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$   $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds.      I think the first step should look something like this:      $d = \gcd(a+b, a-b) = \gcd(2a, a-b)$   From here I tried to proceed with two cases. 1: $a-b$ is even, which leads to $\gcd(a+b, a-b) = 2$ 2: $a-b$ is odd, which leads to $\gcd(a+b, a-b) = 1$  My main problem I think is, that I do not know how I should include $\gcd(a,b) = 1$ in the proof.  Any help is appreciated. Thx in advance. Cherio Woltan
2120
Problem:  If $\gcd(a, b) = 1$ and If $ab = x^2$ ,prove that $a$, $b$ must also be perfect squares; where $a$,$b$,$x$ are in the set of natural numbers  I've come to the conclusion that $a \ne b$ and $a \ne x$ and $b \ne x$ but I guess that won't really help me.. I understand that if the $\gcd$ between two numbers if $1$ then they obviously have no common divisors but where do I go from this point?  Any tips at tackling this would be great. It looks quite easy though I'm still trying to get my hand around these proofs! Any pointers in the right direction would be great.  Thank you in advance,