Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

frx

  • 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
  1. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @myininaya

  2. frx
    • 2 years ago
    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.

  3. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  4. myininaya
    • 2 years ago
    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....

  5. frx
    • 2 years ago
    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

  6. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yeah. lol. I think you are right.

  7. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Woho! :)

  8. frx
    • 2 years ago
    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\]

  9. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    The induction part confuses you?

  10. myininaya
    • 2 years ago
    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 \]

  11. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Wonderful!

  12. frx
    • 2 years ago
    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?

  13. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes :)

  14. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  15. myininaya
    • 2 years ago
    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.

  16. frx
    • 2 years ago
    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}}\]

  17. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  18. myininaya
    • 2 years ago
    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\]

  19. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    They added in a zero.

  20. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Why did the add the zero for?

  21. myininaya
    • 2 years ago
    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

  22. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  23. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    They were setting up for the induction part

  24. myininaya
    • 2 years ago
    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

  25. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the one in expression i wrote before this one

  26. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  27. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok I think I get the whole induction proof now.

  28. frx
    • 2 years ago
    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)\]

  29. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    * given that m<n

  31. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  32. frx
    • 2 years ago
    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 ?

  33. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    no Fn is not equal to 2

  34. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    * F_n is replaces by two *

  35. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  36. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  37. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  38. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  39. myininaya
    • 2 years ago
    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?

  40. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Implies d=1

  41. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Not at all, that made perfect sense actually

  42. frx
    • 2 years ago
    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!

  43. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I try.

  44. frx
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you for your patience, have a great evening!

  45. myininaya
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    You too. :)

  46. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Ask a Question
Find 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
  • 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.