A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 2 years ago
Proove that two Fermat numbers always are relatively prime. I have the lead that F_m  (F_n  2) for m<n.
 2 years ago
Proove that two Fermat numbers always are relatively prime. I have the lead that F_m  (F_n  2) for m<n.

This Question is Closed

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

frx
 2 years ago
Best ResponseYou've already chosen the best response.0I also have this solution but don't understand it neither

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1Hey, 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....

frx
 2 years ago
Best ResponseYou've already chosen the best response.0I 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

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1Yeah. lol. I think you are right.

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

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1The induction part confuses you?

myininaya
 2 years ago
Best 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 \]

frx
 2 years ago
Best ResponseYou've already chosen the best response.0So 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?

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1They are proving it :) Proving that will prove gcd(Fm,Fn)=1

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

frx
 2 years ago
Best ResponseYou've already chosen the best response.0So 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}}\]

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

myininaya
 2 years ago
Best 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\]

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1They added in a zero.

frx
 2 years ago
Best ResponseYou've already chosen the best response.0Why did the add the zero for?

myininaya
 2 years ago
Best 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

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1or F_0F_1F_2...F_(K1)+2

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1They were setting up for the induction part

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

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1the one in expression i wrote before this one

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1We are trying to show F_0F_1....F_k+2

frx
 2 years ago
Best ResponseYou've already chosen the best response.0Ok I think I get the whole induction proof now.

frx
 2 years ago
Best ResponseYou've already chosen the best response.0So 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)\]

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1Please ask any questions if you have them. I like this proof.

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

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

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1no Fn is not equal to 2

frx
 2 years ago
Best ResponseYou've already chosen the best response.0So where does the replacement of F_n to 2 come from?

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

frx
 2 years ago
Best ResponseYou've already chosen the best response.0Sorry don't understand, Isn't that equal to f_(n+1)?

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

myininaya
 2 years ago
Best ResponseYou've already chosen the best response.1Well 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?

frx
 2 years ago
Best ResponseYou've already chosen the best response.0Not at all, that made perfect sense actually

frx
 2 years ago
Best ResponseYou've already chosen the best response.0Will 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!

frx
 2 years ago
Best ResponseYou've already chosen the best response.0Thank you for your patience, have a great evening!
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
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.