數(shù)論課里, 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!
一個星期天的早上，他煮開一壺咖啡禾嫉，準(zhǔn)被看書，然后接到一個朋友的電話科汗，要他幫忙解一個麥當(dāng)勞1百萬美金的數(shù)學(xué)題脐嫂。
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這幾個數(shù)找到和等于100 的整數(shù)解晃酒，
[caption id="attachment_1803" align="alignnone" width="750"]
andreas160578 / Pixabay[/caption]
Dr. Cavior 寫下這幾個數(shù)的時候就笑了澳叉， 因?yàn)樗罌]有整數(shù)解隙咸。
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 最大公約數(shù)
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)
丟番圖方程有解當(dāng)且僅當(dāng) m 被最大公約數(shù)整除。
回到百萬美金賞題 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五督， 這些數(shù)的最大公約數(shù)是3藏否，不能被100整除，所以沒有解
我們用python 來算一下最大公約數(shù)!
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! :)
I m reading Dr.費(fèi)曼's book, he described "他眼中有一束幸福的光. "
我很喜歡這個句子充包， 因?yàn)槲铱匆娺^, 就是 Dr.Cavior 講數(shù)論的時候的眼神!
Next time we will go over how to solve the Linear Diophantine Equations!
Happy Number Theory Learning!
Reference:
Dr.Cavior's Note
https://www.geeksforgeeks.org/gcd-two-array-numbers/
