Linear Diophantine Equation1

In Number Theory Class, Dr.Cavior told us a real story, 

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! 

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.  ✍

andreas160578 / Pixabay

As soon as Dr. Cavior wrote down the numbers, he laughed 🧓,  because there is no way to make integer solutions to add up to 100 with those numbers. 

How did Dr.Cavior figure the answer out so quickly? The secret is the 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)

Back to the problem beginning, because the numbers are 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

we used to learn long division to calculate the gcd, which i hated it so much and i still don’t think i can do it. Luckily now we hat python to check the greatest common divisor for us!

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.Feynman’s book, he described “he eyes were beaming with happiness. ”
I was very touched by this sentence because I have seen the eyes beaming with joy, that’s when Dr.Cavior talking about the Number Theory!

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/

 

  One thought on “Linear Diophantine Equation1

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Social media & sharing icons powered by UltimatelySocial
%d bloggers like this: