Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

frx

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

    @myininaya

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

    Yeah. lol. I think you are right.

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

    Woho! :)

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

    The induction part confuses you?

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

    Wonderful!

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

    Yes :)

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

    They added in a zero.

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

    Why did the add the zero for?

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

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

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

    They were setting up for the induction part

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

    the one in expression i wrote before this one

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

    * given that m<n

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

    no Fn is not equal to 2

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

    * F_n is replaces by two *

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

    Implies d=1

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

    Not at all, that made perfect sense actually

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

    I try.

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

    Thank you for your patience, have a great evening!

  45. myininaya
    • 3 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

Sign Up
Find more explanations on OpenStudy
Privacy Policy