scratch

§ GCD Is at Most Difference of Numbers

created 2021-07-08 · last edited 2022-05-30
  • assume WLOG l<rl< rl<r. Then, Let g≡gcd(l,r)g \equiv gcd(l, r)g≡gcd(l,r). Claim: g≤r−lg \leq r - lg≤r−l.
  • Proof: we have g÷rg \div rg÷r an g÷lg \div lg÷l by definition, hence we must have g÷(r−l)g \div (r - l)g÷(r−l), and ggg, (r−l)(r-l)(r−l) are nonnegative. So g≤(r−l)g \leq (r - l)g≤(r−l).
  • Intuition: the gcd represents the common roots of l,rl, rl,r in Zariski land. That is, if l,rl, rl,r are zero at a prime then so is r−lr - lr−l.
  • So, the GCD equally well represents the common roots of lll and (r−l)(r - l)(r−l).
  • Now, if a number xxx vanishes at a subset of the places where yyy vanishes, we have x<yx < yx<y (the prime factorization of yyy contains all the prime factors of xxx).
  • Since the GCD vanishes at the subset of the roots of lll, a subset of the roots of rrr, and a subset of the roots of (r−l)(r-l)(r−l), it must be smaller than all of these.
  • Thus, the GCD is at most r−lr - lr−l.
  • Why does GCD not vanish at exactly the roots of r−lr-lr−l? If lll and rrr both take the same non-zero value at some prime then (r−l)(r - l)(r−l) does too. But this is not a loacation where lll and rrr vanish.
❦
Newer ৪ Blog ৪ Older