- 4 Fact F Fm Fn M Why Say N M And N Mk R With 0 R M Fm F Fm Fmek 1f Fmkf 1 Fm Fmk 1f 1 (55.52 KiB) Viewed 18 times
4. Fact: (F, Fm) = Fn.m). Why: Say n > m and n= mk+r, with 0
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
4. Fact: (F, Fm) = Fn.m). Why: Say n > m and n= mk+r, with 0
4. Fact: (F, Fm) = Fn.m). Why: Say n > m and n= mk+r, with 0 <r<m: (Fm,F) = (Fm, Fmek +1F, + FmkF,-1) = (Fm, Fmk+1F) = (Fm, F,) = (F, Fm), where r <m is the remainder upon division of n by m and (m,n) = (r,m). Do it again: (F., Fm) = (Fa, F.), where a <r is the remainder upon division of m by r and (r,m) =(a,r). Do it again: (Fa, F.) = (FB, Fa) B<a is the remainder upon division of r by a and (@,r) = (B. a). Etcetera. ... eventually the remainder has to be zero: (F.F.) = (Fr.Fn) = (Fa, F.) = (FB, Fa) = ... =(F. F.) = (0.F.) = F. where (n,m) = (r.m) = (ar) = (B. a) = ... =(0,0) = 0.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!