Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
Proove that two Fermat numbers always are relatively prime. I have the lead that F_m  (F_n  2) for m<n.
 one year ago
 one year ago
Proove that two Fermat numbers always are relatively prime. I have the lead that F_m  (F_n  2) for m<n.
 one year ago
 one year ago

This Question is Closed

frxBest ResponseYou've already chosen the best response.0
I've tried to understand the solution here: https://www.artofproblemsolving.com/Wiki/index.php/Fermat_number but don't really understand it.
 one year ago

frxBest ResponseYou've already chosen the best response.0
I also have this solution but don't understand it neither
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
Hey, so from that link the only thing I don't understand so far is why all of that shows that they are relatively prime. I do understand everything else though.... So still thinking as to why it shows they are....
 one year ago

frxBest ResponseYou've already chosen the best response.0
I thinks it has to do with the fact that every Fermat number is odd so can not be divided by two and hence the only gcd is 1
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
Yeah. lol. I think you are right.
 one year ago

frxBest ResponseYou've already chosen the best response.0
But who do they get the recursion formula from \[F _{n}=2^{2^{n}}+1\]
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
The induction part confuses you?
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
\[F_0=2^{2^0}+1=2^1+1=2+1=3 \] \[F_1=2^{2^1}+1=2^2+1=4+1=5=3+2 \] \[F_2=2^{2^2}+1=2^4+1=16+1=17=15+2 =3(5)+2=F_0 \cdot F_1 +2 \]
 one year ago

frxBest ResponseYou've already chosen the best response.0
So when one have the recursion formula \[F _{n+1}=F _{0}*F _{1}*F _{2}*...*F _{n}+2\] The solution is to show that the recursion formula is correct using induction, right?
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
They are proving it :) Proving that will prove gcd(Fm,Fn)=1
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
If you need help with the algebra, I can do that. Right now, I'm multitasking though...so I will help slowly.
 one year ago

frxBest ResponseYou've already chosen the best response.0
So there are two things I don't understand the first is:\[F _{k+1}=2^{2^{k+1}}+1\] \[=\left( \left( 2^{2^{k}} \right)^{2} +2*2^{2^{k}}+1 \right)  2*2^{2^{k}}\]
 one year ago

frxBest ResponseYou've already chosen the best response.0
The second thing is \[\gcd(F _{m},F _{n})=\gcd(F _{m},2)\]
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
\[=2^{2^{k+1}}+1=2^{2^k2^1}+1=2^{2^k 2}+1=(2^{2^k})^2+1\]
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
They added in a zero.
 one year ago

frxBest ResponseYou've already chosen the best response.0
Why did the add the zero for?
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
\[=(2^{2^k}+1)^2+12 \cdot 2^{2^k} \] So they can write that one part as Fk
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
or F_0F_1F_2...F_(K1)+2
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
They were setting up for the induction part
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
\[=(2^{2^k}+1)(2^{2^k}+1)2^{2^k}\] Ignore that 1oops
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
the one in expression i wrote before this one
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
We are trying to show F_0F_1....F_k+2
 one year ago

frxBest ResponseYou've already chosen the best response.0
Ok I think I get the whole induction proof now.
 one year ago

frxBest ResponseYou've already chosen the best response.0
So seeing that \[F _{k+1}=F _{0}*F _{1}...*F _{k1}*F _{k}+2\] How do I know that \[GCD(F _{m},F _{n})=GCD(F _{m},2)\]
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
Please ask any questions if you have them. I like this proof.
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
Well gcd(odd,2)=1 since odd aren't divisible by 2
 one year ago

frxBest ResponseYou've already chosen the best response.0
Sorry formulated it bad, I mean how do I know that gcd F_n is 2 ?
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
no Fn is not equal to 2
 one year ago

frxBest ResponseYou've already chosen the best response.0
* F_n is replaces by two *
 one year ago

frxBest ResponseYou've already chosen the best response.0
So where does the replacement of F_n to 2 come from?
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
gcd(Fm,Fn) = gcd(Fm,F0F1...F(n1)+2) What about this?
 one year ago

frxBest ResponseYou've already chosen the best response.0
Sorry don't understand, Isn't that equal to f_(n+1)?
 one year ago

frxBest ResponseYou've already chosen the best response.0
Has it to do with the initial lead F_m  (F_n  2) ?
 one year ago

myininayaBest ResponseYou've already chosen the best response.1
Well F_(n+1) equals F0F1....Fn+2  Anyways, Fm(Fn2) =>for some integer k we have k*Fm=Fn2 => k*Fm+2=Fn So gcd(Fm,Fn) = gcd(Fm, k*Fm+2) Let gcd(Fm, k*Fm+2)=d => for some integers a and b we have aFm+b(k*Fm+2)=d Fm(a+bk)+2b=d But a+bk and b are just integers We know gcd(Fm,2)=1 since Fm is odd and isn't divisible by 2. This implies for some integers s and t we have sFm+2t=1 where s above is a+bk and t is b from above. Did this make it more confusing?
 one year ago

frxBest ResponseYou've already chosen the best response.0
Not at all, that made perfect sense actually
 one year ago

frxBest ResponseYou've already chosen the best response.0
Will have to put it all together and solve it 23 times just to make sure it stays in my brain but you're given me the broad understanding, can't thank you enough!
 one year ago

frxBest ResponseYou've already chosen the best response.0
Thank you for your patience, have a great evening!
 one year ago
See more questions >>>
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.