2a4 Math Website
  • Home
    • Basics
    • Methods of Proof>
      • Induction
  • Algebra
    • Binomial Theorem
    • Arithmetic Progression
    • Factorization/Expansion
    • Functions>
      • Absolute Value
      • Logarithms
    • Algebraic Manipulation
    • Inequalities
    • Linear/ Quadratic>
      • Linear Diophantine Equations
      • Quadratic Surds
      • Roots, Coefficients, and Discriminants of Quadratic Expressions
    • Polynomial>
      • Basic Formulas on Polynomials
      • Division of Polynomials
    • Matrices
  • Number Theory
    • Perfect Squares
  • Geometry
    • Geometrical Properties of Circles
    • Midpoint Theorem
    • Triangles>
      • Congruence of Triangles
      • Similarity of Triangles
      • Properties of Triangles and Angles
      • Area & Perimeter of Triangles
      • Centers of a Triangle
      • Basic Trigonometry
    • Radians
    • Intro to Solids
  • SMO
    • SMO 2012 Round 2 Solutions
    • Introduction
  • Weekly Questions
    • Week 1-10>
      • Week 1>
        • Week 1 Solutions
      • Week 2>
        • Week 2 Solutions
      • Week 3>
        • Week 3 Solutions
      • Week 4>
        • Week 4 Solutions
      • Week 5>
        • Week 5 Solutions
      • Week 6>
        • Week 6 Solutions
      • Week 7>
        • Week 7 Solutions
      • Week 8>
        • Week 8 Solutions
      • Week 9>
        • Week 9 Solutions
      • Week 10>
        • Week 10 Solution
    • Week 11>
      • Week 11 Solution

Linear Diophantine Equations

Part 1

This may seem as a big topic, and it is by far the most complex topic of all, because it simply has too many possibilities to consider. One of the famous equations of all time is this:

x^n+y^n=z^n , where x,y,z are unknowns and n is the constant.

We are then asked to solve for x,y,z .

This may seem as a very hard problem to solve, but with enough mathematical knowledge, this can be solved easily. (Solutions are at the end of the whole post–not this post)

Important thing to note:

  • Only integer solutions are allowed for diophantine equations. This narrows the solution range by a lot,and is worth taking note of.
  • A linear diophantine equation generally takes the form of ax+by=c

Before learning anything, we will first introduce a mathematical algorithm, namely the Euclidean Algorithm (Also known as the Euclid’s Algorithm). It is an algorithm commonly used in finding the greatest common divisor(GCD) of two integers a and b .

*Below is the proof for the Euclid’s Algorithm, you may ignore this and continue reading from ##.

To make things easier for us to see, we assume a,b > 0 with a>b .

Therefore, we are safe to say that a=q_0b+r_0 , where 0 leq r_0 < b . Then, find a number u which divides both a and b , so that a = su and b = tu , with s,t be real constants). Then, u also divides r since

r = a - bq=su-qtu=(s-qt)u .

Similarly, find a number v which divides b and r (so that b=s'v and r=t'v ). Then v divides a since

a = bq+r=s'vq+t'v=(s'q+t')v .

Therefore, every common divisor of a and b is a common divisor of b and r . Proceeding recursively, we obtain:

a = q_0b+r_0 with 0 \leq r_0 < b

b = q_1r_0+r_1 with 0 \leq r_1< r_0

r_0 = q_2r_1+r_2 with 0 \leq r_2< r_1

r_1 = q_3r_2+r_3 with 0 \leq r_3< r_2

.

.

Eventually, r_n = 0 for some n , and the algorithm terminates. Therefore, the GCD of a and b is

gcd(r_{n-1},r_n) = gcd (r_{n-1}, 0) = r_{n-1} .

##

If you do not understand the proof, an example of an application of the Euclid’s algorithm is at below:

Let a=2322 and b=654

2322 = 654 \cdot 3 + 360
654 = 360 \cdot 1 + 294
360=294\cdot1+66
294=66\cdot4+30
66=30\cdot2+6
30=6\cdot5
\therefore gcd(2322,654) = 6

Another example:

Let a=5678 and b=1234

5678 = 1234 \cdot 4 + 742
1234 = 742 \cdot 1 + 492
742=492\cdot1+250
492=250\cdot1+242
250=242\cdot1+8
242=8\cdot30+2
8=2\cdot4
\therefore gcd(5678,1234) = 2

After you know this algorithm, you are one step closer in solving linear diophantine equations.

Cheers,

etzhky =)

Part 2

Once you know how to apply the Euclid’s Algorithm, it will be more easier to solve linear diophantine equations involving 2 variables.

Let us see the general form of a linear diophantine equation:

ax+by=c

Does every equation of this form has a solution (x,y) where a,x,b,y,c \in Z ?

Obviously, the answer is no. I will list some counter-examples:

2x+4y=1 ; 3x+6y=2

For the first equation, the L.H.S. is even, where the R.H.S. is odd, which creates a contradiction — there is no solution for (x,y) . Similarly, for the second equation, the L.H.S. is a multiple of three, where the R.H.S. is not, also creates a contradiction which implies that there is also no solution for (x,y) .

This will lead us to a general statement (This is were Euclid’s Algorithm comes in handy) — if gcd(a,b) \nmid c , then (x,y) has no solution. However, when gcd(a,b)|c , (x,y) has infinite solutions. We will see why is the case now. (You can skip this proof and continue reading from ##)

** Proof

Suppose that we have a solution (x_0,y_0) to the equation ax+by=c . Then, the other solutions will be:

x=x_0+b_1t and y=y_0-a_1t , where \forall t \in Z .

Indeed, after we substitute the values inside the original equation,

ax+by=ax_0+ab_1t+by_0-ba_1t=(ax_0+by_0)+(da_1b_1t-db_1a_1t)=c+0=c .

Thus we can deduce that the original equation has infinitely many integers solutions.

Also, let gcd(a,b) be d , thus a=a_1d and b=b_1d , then one solution may be found by determining u,v such that d = ua + vb from the equation ax+by=c , where u,v \in Z .

##

For the sake of convenience, we will say that all other solutions are given by:

\displaystyle{x=x_0+t\cdot\frac{b}{d}} and \displaystyle{y=y_0-t\cdot\frac{a}{d}} , where \forall t \in Z , with \displaystyle{x_0 = u\cdot\frac{c}{d}} and \displaystyle{y_0=v\cdot\frac{c}{d}} .

Take note that d represents gcd(a,b) , and d=ua+vb . Take this as a formula to solve Diophantine equations. Let me use a simple example to make use of this formula.

Example 1

Solve for integer (x,y) :

77x+42y=35

Solution 1

First, we check that whether this equation has integer solutions using the Euclid’s Algorithm:

77 = 42 \cdot 1+35
42 = 35 \cdot 1+7
35 = 7 \cdot 5+0 .

Thus gcd(77,42) = 7 , and since 7|35 , this equation does have integer solutions. To actually find the solutions we need to reverse the steps in Euclid’s Algorithm (I don’t think further explanation is needed because it is relatively easy to understand):

7=42-35 \cdot 1=42-(77-42 \cdot 1)=(-1) \cdot 77+ 2\cdot 42 .

So, we take u=-1 and v=2 (a=77 and b=42 ).

Therefore, applying the formula, all the solutions are

\displaystyle{x_0= -1 \cdot \frac{35}{7} = -5} , \displaystyle{y_0=2\cdot\frac{35}{7}=10} .
\displaystyle{x=x_0+t\cdot\frac{42}{7}=-5+6t}
\displaystyle{y=y_0+t\cdot\frac{77}{7}=10-11t}

where t \in Z .

I shall now use a new example to clarify any doubts.

Example 2

Find all positive integer solutions to the equation 12x+5y=125 .

Solution 2

Note that the question imposed limitations to the solution — it must be positive. So, after getting the general solutions, we must conform to the limitations of the question.

Using the Euclid’s Algorithm,

12 = 5 \cdot 2 + 2
5=2\cdot 2 +1
2=1\cdot 2 + 0.

Thus, gcd(12,5)=1 , and since 1|125 , this equation does have integer solutions. Next, reverse the steps of the Euclid’s Algorithm.

1=5-2\cdot 2=5-2\cdot(12-5\cdot 2) = (-2)\cdot 12 + 5\cdot 5

Thus, we take u=-2 and v=5 .

Thereafter, applying the formula we get the general solution of the equation.

\displaystyle{x_0=-2\cdot\frac{125}{1}=-250} , \displaystyle{y_0=5\cdot\frac{125}{1}=625}
\displaystyle{x=-250+t\cdot\frac{5}{1}=5t-250} ——-(1)
\displaystyle{y=625-t\cdot\frac{12}{1}=625-12t} ———(2)

Since x,y>0 , we get the simultaneous inequality:

5t-250>0
625-12t>0

5t>250
12t<625

t>50
t<52.1

Therefore the range of values for t is 50<t<52.1 , which implies that t=51,52 .

Substitute both values of t into both equations (1), (2), we get:

(x,y)=(5\cdot 51-250,625-12\cdot 51)=(5,13)
(x,y)=(5\cdot 52-250,625-12\cdot 52)=(10,1) .

Thus the equation has two pair of solutions, (5,13) and (10,1) .

For the solution to the equation

x^n+y^n=z^n , where x,y,z are unknowns and n is a non-negative constant,

it has infinite solutions for n=1,2 , but only trivial solutions for n>2 . It is the famous Fermat’s Last Theorem. You can find more about it on the web.

Cheers,
etzhky

Powered by Create your own unique website with customizable templates.