Ace school

with brainly

  • Get help from millions of students
  • Learn from experts with step-by-step explanations
  • Level-up by helping others

A community for students.

Proove that two Fermat numbers always are relatively prime. I have the lead that F_m | (F_n - 2) for m

Mathematics
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

I've tried to understand the solution here: https://www.artofproblemsolving.com/Wiki/index.php/Fermat_number but don't really understand it.
I also have this solution but don't understand it neither

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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....
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
Yeah. lol. I think you are right.
Woho! :)
But who do they get the recursion formula from \[F _{n}=2^{2^{n}}+1\]
The induction part confuses you?
\[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 \]
Wonderful!
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?
Yes :)
They are proving it :) Proving that will prove gcd(Fm,Fn)=1
If you need help with the algebra, I can do that. Right now, I'm multitasking though...so I will help slowly.
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}}\]
The second thing is \[\gcd(F _{m},F _{n})=\gcd(F _{m},2)\]
\[=2^{2^{k+1}}+1=2^{2^k2^1}+1=2^{2^k 2}+1=(2^{2^k})^2+1\]
They added in a zero.
Why did the add the zero for?
\[=(2^{2^k}+1)^2+1-2 \cdot 2^{2^k} \] So they can write that one part as Fk
or F_0F_1F_2...F_(K-1)+2
They were setting up for the induction part
\[=(2^{2^k}+1)(2^{2^k}+1)-2^{2^k}\] Ignore that 1oops
the one in expression i wrote before this one
We are trying to show F_0F_1....F_k+2
Ok I think I get the whole induction proof now.
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)\]
Please ask any questions if you have them. I like this proof.
* given that m
Well gcd(odd,2)=1 since odd aren't divisible by 2
Sorry formulated it bad, I mean how do I know that gcd F_n is 2 ?
no Fn is not equal to 2
* F_n is replaces by two *
So where does the replacement of F_n to 2 come from?
gcd(Fm,Fn) = gcd(Fm,F0F1...F(n-1)+2) What about this?
Sorry don't understand, Isn't that equal to f_(n+1)?
Has it to do with the initial lead F_m | (F_n - 2) ?
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?
Implies d=1
Not at all, that made perfect sense actually
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!
I try.
Thank you for your patience, have a great evening!
You too. :)

Not the answer you are looking for?

Search for more explanations.

Ask your own question