Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

frx Group Title

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
  1. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @myininaya

    • one year ago
  2. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  3. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I also have this solution but don't understand it neither

    • one year ago
  4. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  5. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  6. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yeah. lol. I think you are right.

    • one year ago
  7. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Woho! :)

    • one year ago
  8. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    But who do they get the recursion formula from \[F _{n}=2^{2^{n}}+1\]

    • one year ago
  9. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    The induction part confuses you?

    • one year ago
  10. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  11. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Wonderful!

    • one year ago
  12. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  13. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes :)

    • one year ago
  14. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    They are proving it :) Proving that will prove gcd(Fm,Fn)=1

    • one year ago
  15. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  16. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 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
  17. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    The second thing is \[\gcd(F _{m},F _{n})=\gcd(F _{m},2)\]

    • one year ago
  18. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[=2^{2^{k+1}}+1=2^{2^k2^1}+1=2^{2^k 2}+1=(2^{2^k})^2+1\]

    • one year ago
  19. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    They added in a zero.

    • one year ago
  20. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Why did the add the zero for?

    • one year ago
  21. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[=(2^{2^k}+1)^2+1-2 \cdot 2^{2^k} \] So they can write that one part as Fk

    • one year ago
  22. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    or F_0F_1F_2...F_(K-1)+2

    • one year ago
  23. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    They were setting up for the induction part

    • one year ago
  24. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[=(2^{2^k}+1)(2^{2^k}+1)-2^{2^k}\] Ignore that 1oops

    • one year ago
  25. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    the one in expression i wrote before this one

    • one year ago
  26. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    We are trying to show F_0F_1....F_k+2

    • one year ago
  27. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok I think I get the whole induction proof now.

    • one year ago
  28. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    So seeing that \[F _{k+1}=F _{0}*F _{1}...*F _{k-1}*F _{k}+2\] How do I know that \[GCD(F _{m},F _{n})=GCD(F _{m},2)\]

    • one year ago
  29. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Please ask any questions if you have them. I like this proof.

    • one year ago
  30. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    * given that m<n

    • one year ago
  31. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Well gcd(odd,2)=1 since odd aren't divisible by 2

    • one year ago
  32. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry formulated it bad, I mean how do I know that gcd F_n is 2 ?

    • one year ago
  33. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    no Fn is not equal to 2

    • one year ago
  34. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    * F_n is replaces by two *

    • one year ago
  35. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    So where does the replacement of F_n to 2 come from?

    • one year ago
  36. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    gcd(Fm,Fn) = gcd(Fm,F0F1...F(n-1)+2) What about this?

    • one year ago
  37. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry don't understand, Isn't that equal to f_(n+1)?

    • one year ago
  38. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Has it to do with the initial lead F_m | (F_n - 2) ?

    • one year ago
  39. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Well F_(n+1) equals F0F1....Fn+2 ---- Anyways, Fm|(Fn-2) =>for some integer k we have k*Fm=Fn-2 => 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
  40. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Implies d=1

    • one year ago
  41. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Not at all, that made perfect sense actually

    • one year ago
  42. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Will have to put it all together and solve it 2-3 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
  43. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I try.

    • one year ago
  44. frx Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you for your patience, have a great evening!

    • one year ago
  45. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You too. :)

    • one year ago
    • Attachments:

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.