麦当劳里的丢番图方程 Linear Diophantine Eq

数论课里, Dr.Cavior 讲过一个真的故事,

One Sunday morning 🌞, he just made a cup of freshly brewed coffee☕ and started to read a book 📒, then he got a call from a friend ☎. The friend was asking for his help with a 1 Million Dollars McDonald's Puzzle that she was trying for couple days!
一个星期天的早上，他煮开一壶咖啡，准被看书，然后接到一个朋友的电话，要他帮忙解一个麦当劳1百万美金的数学题。

The 1 Million Dollar Puzzle was using any integer coefficients to make a sum of 100 with 3, 48, 6, 21, 33, 18, 36, 12, 60. ✍

用3, 48, 6, 21, 33, 18, 36, 12, 60这几个数找到和等于100 的整数解，

[caption id="attachment_1803" align="alignnone" width="750"] L

andreas160578 / Pixabay[/caption]

Dr. Cavior 写下这几个数的时候就笑了， 因为他知道没有整数解。

Dr.Cavior 怎么能这么快知道答案？ 秘密就是 Linear Diophantine Equation! 丢番图方程

We will go over the basic theorem of GCD(greatest common divisor) and Diophantine Linear Equation now.

• Linear Diophantine Equation 丢番图

Simple Form: ax+by=c, where a, b, and c are integers
General Form: ax1+bx2+cx3+dx4.....=m, where a,b,c.. are integer coefficients.

• Greatest Common Divisor 最大公约数

  d is the greatest common divisor of integers a and b if d is the largest positive integer which divides both a and b.
  Notation d= gcd(a,b)
  Example 4=gcd(8,12)

• Linear Diophantine Equation Solution Theorem 丢番图方程定理

  For any Non-zero Integer a and b, ax+by=c, there exist integer solutions if and only if c|gcd(a,b).
  More generally, a1x1+a2x2+a3x3+.... anxn=m, there exist integer solution if and only if m|gcd(a1,a2,...an)
  丢番图方程有解当且仅当 m 被最大公约数整除。

回到百万美金赏题 3, 48, 6, 21, 33,18,36,12,60. the greatest common divisor of these number is 3, which is not divisible by 100, so this is no solutions， 这些数的最大公约数是3，不能被100整除，所以没有解

我们用python 来算一下最大公约数!

def find_gcd(x,y):
    while(y):
        x,y =y , x%y
    return x
l=[3,6,18,21]
num1=l[0]
num2=l[1]
gcd=find_gcd(num1,num2)
for i in range(2, len(l)):
    gcd=find_gcd(gcd,l[i])
print(gcd)

3

I still remember Dr. Cavior said it is pretty Wicked for McDonald's to put down puzzles like that! :)

image

I m reading Dr.费曼's book, he described "他眼中有一束幸福的光. "
我很喜欢这个句子， 因为我看见过, 就是 Dr.Cavior 讲数论的时候的眼神!

Next time we will go over how to solve the Linear Diophantine Equations!

Happy Number Theory Learning!

image

Reference:
Dr.Cavior's Note
https://www.geeksforgeeks.org/gcd-two-array-numbers/