Unit - 1

Linear Diophantine equation

1.1 Linear Diophantine equation

A Diophantine problem is one in which all of the answers must be integers. I'll use the word Diophantine equations to refer to equations that must be solved over the integers.

For example, the equation   has many solutions over the reals. Here's a solution:

However, there are no nonzero integer solutions to this equation. Fermat's Last Theorem has a specific instance.

The following equation, on the other hand, has an endless number of integer solutions:

 and  are examples of solutions.

In this section, I'll look at equations like the last one. They're called linear Diophantine equations.

Theorem. Let  . Consider the Diophantine equation

(a) If does divide c, there are no solutions.

(b) If  , there are infinitely many solutions of the form

Here  is a particular solution, and .

If you've had a course in differential equations, you may have seen something like this.  and   give a general solution to the homogeneous equation

 is a particular solution to  . Their sum gives a general solution to the given (nonhomogeneous) equation.

Before I give the proof, I'll give some examples, and also discuss the three variable equation .

Example. Find the general solution to the following Diophantine equation.

Let  .

 and  is a particular solution. So

and

Then

and is a particular solution. The general solution is

A general linear Diophantine equation has the form

There are solutions if  . If there is a solution, it will in general have  parameters --- exactly as you'd expect from linear algebra.

Here's the proof of the theorem for the two-variable case.

Proof. (two variable case) Consider the linear Diophantine equation

Case 1. Suppose (a,b) does not divide c . If x and y are solutions to the equation, then

This contradiction shows that there cannot be a solution.

Case 2. Suppose . Write  for  . There are integers m and n such that

Then

Hence,  , is a solution.

Suppose  ,  , is a particular solution. Then

This proves that  is a solution for every  .

Finally, I want to show that every solution has this form. Suppose then that (x,y) is a solution. Then  and  imply

Therefore,

Now  divides the left side, so it divides the right side. However,  . Therefore,

for some

Thus,

Substitute  back into the last x-y equation above:

Thus,

and

Key takeaways:

• The goal of any Diophantine equation is to solve for all of the problem's unknowns. Diophantus would try to write all the unknowns in terms of only one of them when he was dealing with two or more unknowns.
• Equations including more than two variables Consider the three-variable linear Diophantine equation an x + b y + c z = d. Axe + by + cz = d. Ax+by+cz=d.

1.2 Prime counting function

The function  giving the number of Primes less than  (Shanks 1993, p. 15). The first few values are 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (Sloane's A000720). The following table gives the values of  for powers of 10 (Sloane's A006880; Hardy and Wright 1979, p. 4; Shanks 1993, pp. 242-243; Ribenboim 1996, p. 237). Deleglise and Rivat (1996) have computed .

• The goal of any Diophantine equation is to solve for all of the problem's unknowns. Diophantus would try to write all the unknowns in terms of only one of them when he was dealing with two or more unknowns.

• Equations including more than two variables Consider the three-variable linear Diophantine equation an x + b y + c z = d. Axe + by + cz = d. Ax+by+cz=d.

 In Hardy and Wright, the number is wrongly stated as 50,847,478. (1979). Legendre's Formula, Lehmer's Formula, Mapes' Method, and Meissel's Formula can all be used to represent the prime counting function. A brief history of attempts to calculate  is given by Berndt (1994). The following table is taken from Riesel (1994).

Method	Time	Storage
Legendre
Meissel
Lehmer
Mapes'
Lagarias-Miller-Odlyzko
Lagarias-Odlyzko 1
Lagarias-Odlyzko 2

A modified version of the prime counting function is given by

Where  is the Möbius Function and  is the Riemann-Mangoldt Function.

The notation  is also used to denote the number of Primes of the form  (Shanks 1993, pp. 21-22). Groups of Equinumerous values of 

Include (,), (,), (,,, ), (,), (,, ,, ,), (,, ,), (, , , ,,), and so on. The values of  for small  are given in the following table for the first few powers of ten (Shanks 1993).

	1	2	1	2
	11	13	11	13
	80	87	80	87
	611	617	609	619
	4784	4807	4783	4808
	39231	39266	39175	39322
	332194	332384	332180	332398

	0	2	1	0
	5	7	7	5
	40	47	42	38
	306	309	310	303
	2387	2412	2402	2390
	19617	19622	19665	19593
	166104	166212	166230	166032

	1	1
	11	12
	80	86
	611	616
	4784	4806
	39231	39265

	0	1	1	0	1	0
	3	4	5	3	5	4
	28	27	30	26	29	27
	203	203	209	202	211	200
	1593	1584	1613	1601	1604	1596
	13063	13065	13105	13069	13105	13090

	0	1	1	1
	5	7	6	6
	37	44	43	43
	295	311	314	308
	2384	2409	2399	2399
	19552	19653	19623	19669
	165976	166161	166204	166237

Note that since , and  are Equinumerous,

	=
	=

Are also equinumerous.

Erdös proved that there exist at least one Prime of the form 4k+1 and at least one Prime of the form 4k+3 between n and 2n for all n>6.

1.3 Statement of prime number theorem

The prime number theorem is a formula that estimates the number of primes that are less than or equal to a given positive real number x. This number is usually written as (x), so (2) = 1, (3.5) = 2, and (10) = 4. The prime number theorem asserts that (x) is approximately equal to x/ln for high values of x. (x). For various values of x, the table compares the actual and projected number of primes.

The mathematical features of prime numbers were first studied by ancient Greek mathematicians. (Many people had previously examined such numbers for their mystical or spiritual properties.) While many people have remarked that primes appear to “thin out” as numbers get larger, Euclid may have been the first to prove that there is no biggest prime; in other words, there are an unlimited amount of primes in his Elements (c. 300 BC). Over the years that followed, mathematicians tried and failed to establish a formula that would allow them to generate an infinite number of primes. Others began to conjecture about formulas that could describe the general distribution of primes after failing to find an explicit formula. The prime number theorem was initially proposed in 1798 by French mathematician Adrien-Marie Legendre as a conjecture. Legendre claimed that x/(ln(x) 1.08366) is very close to x/(ln(x) 1.08366) if x is not more than 1,000,000, based on his analysis of a table of primes up to 1,000,000. (x). The prime number theorem, which states the result for constant 0, is essentially equal to this result for any constant, not simply 1.08366. However, it is now recognised that for relatively small x, the constant that offers the best approximation to (x) is 1.

In his notebook, maybe around 1800, the eminent German mathematician Carl Friedrich Gauss conjectured an equivalent of the prime number theorem. The theorem was not proved until 1896, when French mathematicians Jacques-Salomon Hadamard and Charles de la Valée Poussin separately demonstrated that the ratio x/ln(x) equals infinity in the limit (as x increases to infinity) (x).

Although the prime number theorem states that as x grows larger, the difference between (x) and x/ln(x) becomes vanishingly small in comparison to the magnitude of either of these numbers, one can still request an estimate of that difference. Square root of x ln is thought to be the best estimate of this discrepancy (x).

Examples:

1) Estimate the number of prime numbers between 2 million and 7 million using the Prime Number Theorem.

Solution:

The number of primes between 2000000 and 7000000

= π(7000000) − π(1999999)

≈ 7000000/ log(7000000) − 1999999/ log(1999999)

≈ 306274.

The exact answer is 327715, so we are about 6.5% out.

2) Calculate ϕ(n) for n = 1200 and n = 2008.

Solution:

3) Let n ∈ N and let p be a prime. Show that if p | n then ϕ(np) = pϕ(n). Hint: consider the prime factorization of n.

Solution:

Since p | n, the prime factorization of n is

For some k. Thus

1.4 Goldbach conjecture

"At least it seems that every integer bigger than 2 is the sum of three primes," Goldbach's original conjecture (also known as the "ternary" Goldbach conjecture) asserts in a June 7, 1742 letter to Euler (Goldbach 1742; Dickson 2005, p. 421). It's worth noting that Goldbach thought 1 to be a prime number, which is no longer the case. An equivalent form of this claim (known as the "strong" or "binary" Goldbach conjecture) asserts that all positive even numbers may be written as the sum of two primes, as re-stated by Euler. A Goldbach partition is a pair of primes that together form a positive integer (Oliveira e Silva).

"It is very easy to make good predictions," writes Hardy (1999, p. 19). "Indeed, there are theorems, like 'Goldbach's Theorem,' which have never been proved and which any fool could have guessed." Between March 20, 2000 and March 20, 2002, Faber and Faber offered a prize to anyone who could prove Goldbach's conjecture, but the prize went unclaimed, and the conjecture remains open.

Schnirelman (1939) proved that each even integer may be expressed as the sum of not more than primes (Dunham 1990), which appears to be a long way from a proof for two primes! Pogorzelski (1977) claimed to have proved the Goldbach conjecture, but his proof is widely regarded as insufficient (Shanks 1985). The bounds that have been demonstrated to be true for numbers so that the strong Goldbach conjecture is true are summarised in the table below.

Bound	Reference
	Desboves 1885
	Pipping 1938
	Stein and Stein 1965ab
	Granville et al. 1989
	Sinisalo 1993
	Deshouillers et al. 1998
	Richstein 1999, 2001
	Oliveira e Silva (Mar. 24, 2003)
	Oliveira e Silva (Oct. 3, 2003)
	Oliveira e Silva (Feb. 5, 2005)
	Oliveira e Silva (Dec. 30, 2005)
	Oliveira e Silva (Jul. 14, 2008)
	Oliveira e Silva (Apr. 2012)

The "weak" Goldbach conjecture states that all odd numbers are equal to the sum of three odd primes. Vinogradov (1937ab, 1954) proved that each sufficiently large odd number is the sum of three primes (Nagell 1951, p. 66; Guy 1994), and Estermann (1938) proved that practically all even numbers are the sums of two primes (Nagell 1951, p. 66; Guy 1994). "Sufficiently large" was Vinogradov's original phrase.   was subsequently reduced to  by Chen and Wang (1989). Chen (1973, 1978) further demonstrated that any sufficiently big even numbers are the product of at most two primes and the sum of a prime (Guy 1994, Courant and Robbins 1996). Helfgott proved the weak Goldbach conjecture more than two and a half centuries after the original guess was made (2013, 2014).

Levy's conjecture is a stronger variant of the weak hypothesis, stating that any odd number may be written as the sum of a prime plus twice a prime.

The Goldbach conjecture's corresponding statement is that there are primes and such for every positive integer.

Where  is the totient function (e.g., Havil 2003, p. 115; Guy 2004, p. 160). (This follows immediately from  for p prime.) Erdős and Moser have considered dropping the restriction that p and q be prime in this equation as a possibly easier way of determining if such numbers always exist.

Other variants of the Goldbach conjecture include the statements that every even number  is the sum of two odd primes, and every integer >17 the sum of exactly three distinct primes.

Let be the number of representations of an even number n as the sum of two primes. Then the "extended" Goldbach conjecture states that

Where  is the twin primes constant.

Key takeaways:

• According to the Goldbach conjecture, every even integer is the sum of two primes. Despite the fact that it is obviously correct, this supposition was suggested in 1742 and has yet to be confirmed.

• A nontrivial additive property of primes is asserted by Goldbach.

• The challenge occurs when moving from the multiplicative to additive structure of numbers.

1.5 Linear congruences

A linear congruence equation

 (1)

Is solvable iff the congruence

 (2)

With  is the greatest common divisor is solvable. Let one solution to the original equation be . Then the solutions are  If , then there is only one solution <m.

The solution of a linear congruence can be found in the Wolfram Language using Reduce[a*x == b, x, Modulus -> m].

Finding the value of a fractional congruence, for which a greedy-type solution exists, is comparable to solving a linear congruence problem. (1), for example, can be rewritten as

 (3)

Which can also be written

 (4)

The answer can be found as Mod[b y, m] of the Power Mod[a,, m] solution produced by the Wolfram Language function. A modular inverse is what this is called.

Two or more linear congruences occur at the same time.

 (5)

 (6)

Are solvable using the Chinese remainder theorem.

Example:

1) Solve  .

Solution:

Since  , there are no solutions.

2)  Solve  .

Solution:

Since  , there will be 1 solutions mod 4. I'll find it in three different ways.

Using Diophantine equations that are linear.

implies 3x+4y=7 for some y.

By inspection  ,  is a particular solution.  , so the general solution is

The y equation has no bearing. According to the x equation,

Using the Euclidean algorithm. Since   , some linear combination of 3 and 4 is equal to 1. In fact,

This tells me how to juggle the coefficient of x to get 1  x:

(I used the fact that .

Here is a multiplication table with inverses mod 4:

I see that  , so I multiply the equation by 3:

3) Solve

Solution:

 , so there are  solutions mod 10. I'll solve the equation using a reduction trick similar to the one I used to solve two variable linear Diophantine equations.

The following equation is the same as

Set

Then

 ,  , is a particular solution. The general solution is

Substitute for w:

 , is a particular solution. The general solution is

 will produce distinct values of y mod 10. Note, however, that s and  produce  and  , which are congruent mod 10. That is, adding a multiple of 2 to a given value of s makes the  term in x repeat itself mod 10. So I can get all possibilities for x mod 10 by letting .

All together, the distinct solutions mod 10 are

Remarks: I saw the particular solution  by inspection. In general, you can get one using the Extended Euclidean algorithm. For example, in this case

Multiply by  (to match  ) to get

)

So a particular solution is  and   .

1.6 Complete set of residues

A set of numbers that satisfy the following criterion is known as a complete residue system modulo. Every integer modulo is congruent to a single member of the set.

In other words, each residue class has exactly one member in the set.

A set of numbers  (mod m) form a complete set of residues, also called a covering system, if they satisfy

For i=0, 1, ..., m-1. For example, a complete system of residues is formed by a base  and a modulus  if the residues  in  for ,  run through the values 1, 2, ..., m-1.

1.7 Chinese remainder theorem

Let and  be positive integers which are relatively prime and let a and b be any two integers. Then there is an integer  such that

 (1)

And

 (2)

Moreover, N is uniquely determined modulo r s. An equivalent statement is that if , then every pair of residue classes modulo r and s corresponds to a simple residue class modulo r s.

The Chinese remainder theorem is implemented in the Wolfram Language as Chinese Remainder[{a1, a2, ...}{m1, m2, ...}]. Reduce in with an Integers domain specification is also used to apply the Chinese remainder theorem indirectly.

The following is a generalisation of the theorem. Given a set of congruences that occur at the same time,

 (3)

For  and for which the  are pairwise relatively prime, the solution of the set of congruences is

 (4)

Where

 (5)

And the  are determined from

Numerical’s:

Solve the system

N=2.3.5=30 is the number we have. Also

…………(1)

As a result, we must now solve 15y1(mod 2)15.

……(2)

In the same way, we find that

…….(3)

As a result, we end up with

……(4)

2) Find all solutions of x2 ≡ 1 (mod 144).

Solution:

144 = 16⋅9 = and gcd(16,9) = 1.

Two simultaneous congruences can be used to replace our congruence:

X2 ≡ 1 (mod 16) has 4 solutions: x ≡ ±1 or ±7 (mod 16)

x 2 ≡ 1 (mod 9) has 2 solutions: x ≡ ±1 (mod 9)

There are 8 alternatives:

With k = 2, m1 = 16, and m2 = 9, each case above has a unique solution for x modulo 144, according to the Chinese Remainder Theorem.

We arrive at the following conclusion:

The following are the eight options:

1.8 Fermat's little theorem

If  is a prime number and  is a natural number, then

 (1)

Furthermore, if  (p does not divide a), then there exists some smallest exponent d such that

 (2)

And d divides p-1.Hence,

  (3)

The theorem is sometimes also simply known as "Fermat's theorem" (Hardy and Wright 1979, p. 63).

This is a specific example of Euler's totient theorem and a generalisation of the Chinese hypothesis. It's also known as Fermat's primality test, and it's a required but insufficient test for primality. The first proof was published by Euler in 1749, despite the fact that it was apparently proved (but suppressed) by Fermat. The term "Fermat's small theorem" was initially used to characterise the theorem in a German textbook by Hensel (1913), and it also appears in Mac Lane (1940) and Kaplansky (1941). (1945).

The theorem is easily proved using mathematical induction on . Suppose  (i.e.,  divides ). Then examine

(4)

From the binomial theorem,

 (5)

Rewriting,

 (6)

But p divides the right side, so it also divides the left side. Combining with the induction hypothesis gives that p divides the sum

 (7)

Assume that the hypothesis is correct for any. Fermat's simple theorem is another name for the theorem. Wilson's theorem follows Fermat's small theorem as a corollary.

Fermat's little theorem shows that, if  is prime, there does not exist a base  with  such that  possesses a nonzero residue modulo p. If such base a exists, p is therefore guaranteed to be composite. However, the lack of a nonzero residue in Fermat's little theorem does not guarantee that p is prime. Fermat's little theorem is frequently referred to as the Fermat compositeness test since it has the property of indisputably certifying composite numbers while passing some primes. A probable prime is a number that fulfils Fermat's little theorem for some nontrivial base and is not known to be composite.

Fermat pseudoprimes (or simply "pseudoprimes") are composite numbers that have zero residue for some s and hence are not identified as composite. Worse still, there exist numbers known as Carmichael numbers (the smallest of which is 561) which give zero residue for any choice of the base a relatively prime to p. However, Fermat's little theorem converse provides a criterion for certifying the primality of a number. A table of the smallest pseudoprimes for the first 100 bases  follows.

2	341	22	69	42	205	62	63	82	91
3	91	23	33	43	77	63	341	83	105
4	15	24	25	44	45	64	65	84	85
5	124	25	28	45	76	65	112	85	129
6	35	26	27	46	133	66	91	86	87
7	25	27	65	47	65	67	85	87	91
8	9	28	45	48	49	68	69	88	91
9	28	29	35	49	66	69	85	89	99
10	33	30	49	50	51	70	169	90	91
11	15	31	49	51	65	71	105	91	115
12	65	32	33	52	85	72	85	92	93
13	21	33	85	53	65	73	111	93	301
14	15	34	35	54	55	74	75	94	95
15	341	35	51	55	63	75	91	95	141
16	51	36	91	56	57	76	77	96	133
17	45	37	45	57	65	77	247	97	105
18	25	38	39	58	133	78	341	98	99
19	45	39	95	59	87	79	91	99	145
20	21	40	91	60	341	80	81	100	153
21	55	41	105	61	91	81	85

Example: 

1) Calculate mod 11 efficiently using Fermat’s Little Theorem. Solution. The number 2 is not divisible by the prime 11, so

By Fermat’s Little Theorem. According to the division algorithm,

Since

Then,

Thus,

The following corollary to Fermat's Little Theorem is actually required for RSA encryption.

2) Show that the inverse of 5 modulo 101 is 599

Solution:

5 100 ≡ 1 (mod 101),

So

5 99 · 5 ≡ 5 · 5 99 ≡ 1 (mod 101),

Which by definition means that 599 is the inverse of 5 modulo 101.

3) Use repeated squaring to simplify 599 (mod 101).

Solution:

Thus

4) Hence solve the equation (mod 101).

Solution:

x ≡ 5 −1 · 31 ≡ 81 · 31 ≡ 87 (mod 101).

Check:

5 · 87 = 435 ≡ 31 (mod 101).

5) To solve the following system of equivalences, find the two least positive integer solutions.

x ≡ 2 (mod 5)

x ≡ 5 (mod 8)

x ≡ 4 (mod 37)

Solution:

This is an example of how the CRT can be used directly: M1 = 8 • 37 = 296 M2 = 5 • 37 = 185 M3 = 5 • 8 = 40 M1 = 8 • 37 = 296 M2 = 5 • 37 = 185 M3 = 5 • 8 = 40

M1 (one) (mod 5) m2 = one (mod 8) M3 (three) (mod 37)

1 (mod 5) 1 (mod 8) 3 • 25 0 (mod 37),

As a result, N1 = 1, N2 = 1, and N3 = 25.

Thus, 5517 1077 (mod 5 • 8 • 37) = x 2 • 296 • 1 + 5 • 185 • 1 + 4 • 40 • 25 = 5517 1077 (mod 5 • 8 • 37). If an integer is in this congruence class modulo 5 • 8 • 37 = 1480, it fulfils the system of congruences. 1077 and 2557 are the two smallest positive numbers in this congruence class.

Key takeaways:

• It is a specific case of Euler's theorem and is useful in elementary number theory applications such as primality checking and public-key cryptography.

1.9 Wilson's theorem

Iff  is a prime, then  is a multiple of , that is

 (1)

Although it was previously known to Leibniz, this theorem was proposed by John Wilson and published by Waring (1770). Lagrange demonstrated it in 1773. Wilson's theorem, unlike Fermat's small theorem, is both necessary and sufficient for primality. When calculating a composite number,  except when .

A corollary to the theorem states that iff a prime p is of the form 4k+1, then

 (2)

The first few primes of the form  are , 13, 17, 29, 37, 41, ... (OEIS A002144), corresponding to k=1, 3, 4, 7, 9, 10, 13, 15, 18, 22, 24, 25, 27, 28, 34, 37, ... (OEIS A005098).

Gauss's generalization of Wilson's theorem considers P(n) the product of integers that are less than or equal to and relatively prime to an integer n. For n=1, 2, ..., the first few values are 1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, ... (OEIS A001783). Then defining

 (3)

Gives the congruence

For p an odd prime. When n=2, this reduces to P which is equivalent to . The first few values of   are 0, -1, -1, -1, -1,-1,-1, 1,-1, -1 -1, ... (OEIS A103131).

Szántó (2005) notes that defining

        (5)

         (6) 

Then, taking the minimal residue,

 (7)

For  the first terms are then 0, -1, 1, 1, 0,-1, 1, 0, -1, -1, 0, ...

Examples:

1) Find the remainder of 97! when divided by 101.

Solution:

First, we'll use Wilson's theorem to determine that 100!1 (mod101). We obtain the following when we decompose the factorial:

Now we can see that 1001(mod101), 992(mod101), and 983 are all mod101 (mod101). Hence:

  ……….(2)

Now we want to find a modular inverse of 6 (mod 101). Using the division procedure, we arrive to the following:

……………..(3)

As a result, 17 can be used as the inverse of 6. (mod 101). The following is the result:

……………(4)

Hence, 97! has a remainder of 17 when divided by 101.

2) Find the remainder of 67! when divided by 71.

Solution:

Using Wilson's theorem, we have that 70!≡−1(mod71). Decomposing the factorial we get that:

 …………..(5)

Let's use the division procedure to obtain the modular inverse of 6 (mod 71).:

   ……………………(6)

As a result, 12 can be used as the inverse. Thus:

 …………………(7)

Hence when 67! is divided by 71, the remainder leftover is 12.

3) Find the remainder of 53! when divided by 61.

Solution:

We know that by Wilson's theorem 60!≡−1(mod61). Decomposing 60!, we get that:

 …….……(8)

To find a modular inverse of 52 (mod 61), we'll utilise the division algorithm:

……………….(9)

As a result, 27 can be used as the inverse (mod 61). As a result, we have:

………………….(10)

4) What is the remainder of 149! when divided by 139?

Wilson's theorem tells us that 138!1 (mod139). We will now multiply both sides of the congruence till we reach 149! :

…….(11)

Hence the remainder of 149! when divided by 139 is 0.

In fact, this should make sense, since 149! = 149 x 148 x … x 139 x 138 x … x 2 x 1. For any primes p and q where , it follows that 

Q. 5x−3y=0,x,y∈Z5x−3y=0,x,y∈Z.

Solution

In this case x=3x=3, y=5y=5 is a solution as is x=6x=6, y=10y=10.

Hence x=3kx=3k and y=5k,k∈Zy=5k,k∈Z represent all the solutions.

Check: 5(3k)−3(5k)=15k−15k=0.5(3k)−3(5k)=15k−15k=0.

**** NOTE**** In a homogeneous linear diophantine equation, the minute the equation is an addition, one of the variable is required to be negative.
In the case

Of 5x+3y=0,x,y∈Z5x+3y=0,x,y∈Z, x=−3kx=−3k and y=5k,k∈Zy=5k,k∈Z are solutions.

Q. 6x+9y=0,x,y∈Z.

Solution:

Note that GCD of 6 and 9 is 3. Hence the solutions are x=9k3=3k  and  y=−6k3=−2k  with  k∈Z . Use the following steps to solve a non-homogeneous linear Diophantine equation.

Solve the linear Diophantine Equations:  ax+by=c,x,y∈Z .

Use the following steps to solve a non-homogeneous linear Diophantine equation.

Step 1: Determine the GCD of a and b. Let suppose  gcd(a,b)=d .

Step 2: Check that the GCD of a and b divides c. NOTE: If YES, continue on to step 3. If NO, STOP as there are no solutions.

Step 3: Find a particular solution to  ax+by=c  by first finding  x0,y0  such that  ax+by=d . Suppose  x=cdx0  and  y=cdy0 .

Step 4: Use a change of variables: Let  u=x−cdx0  and  v=y−cdy0 , then we will see that  au+bv=0  (important to check your result).

Step 5: Solve  au+bv=0 . That is:  u=−bdm  and  v=adm,m∈Z .

Step 6: Substitute for  u  and  v . Thus the general solutions are  x−cdx0=−bdm  and  y−cdy0=adm,m∈Z .

Q. Solve the linear Diophantine Equations:  5x+3y=4,x,y∈Z .

Solution:

Step 1: Determine the GCD of 5 and 3 (a and b). Since  5(2)+3(−3)=1 ,  gcd(5,3)=1.

Step 2: Since  1∣4 , we will continue on to Step 3.

Step 3: Find a particular solution to  5x+3y=4,x,y∈Z .

Since 5(5)+3(−7)=4,x=5  and  y=−7  is a particular solution.

Step 4: Let  u=x−5  and  v=y+7.  Note: The opposite integer of Step 4, so if it's positive in step 4 it will be negative in step 5 and vice versa.

Then  5u+3v=5(x−5)+3(y+7)

=5x−25+3y+21

=5x+3y−4

=4−4  (because the equation is  5x+3y=4 )

=0.

Step 5: Solve 5u+3v=0

The general solutions are  u=−3m  and  v=5m,m∈Z .

Step 6:  x−5=−3m  and  y+7=5m,m∈Z .

Hence the general solutions are  x=−3m+5,y=5m−7,m∈Z .

Q. Solve the linear Diophantine Equations:  2x+4y=21,x,y∈Z .

Solution:

Since  gcd(2,4)=2  and  2  does not divide  21 ,  2x+4y=21  has no solution.

Q. Solve the linear Diophantine Equation  20x+16y=500,x,y∈Z+ .

Solution

Both  x,y≥0.500=20(x)+16(y).

Step 1:  gcd(20,16)=4.  Since  4|500 , we expect a solution.

Step 2: A solution is  4125=20(1)(125)+16(−1)(125).

500=20(125)+16(−125)

Hence,  x=125  and  y=−125  is a solution to  500=20x+16y.

Step 3: Let u = x - 125 and v = y + 125.

Consider that 20u + 16v =20x - (20)(125) + 16y +(16)(125)

=20x +16y -[(20)(125) -(16)(125)]

=20x + 16y -500.

Thus, 20u + 16v = 0.

Step 4: In general, the solution to ax + by = 0 is x=bdk and y=-adk, kZ \ {0}, d=gcd(a,b). Recall, gcd(20, 16) = 4.

Thus u = 16k/4 = 4k and v = -20k/4 = -5k, k ∈ ℤ.

Step 5: Replace u and v.

Consider 4k = x - 125 and -5k = y + 125.

Hence, x = 4k + 125 and y = -5k - 125.

Step 6: Both x and y ≥ 0. x ≤ 25 and y ≤ 31 since total is 500.

4k + 125 ≥ 0, k ≥ -125/4, ∴ k ≥ -31.25.

4k + 125 ≤ 25, 4k ≤ -100, ∴ k ≤ -25.

Thus, the possible solutions are:

Let k = -25 then x = 25, y = 0.

Let k = -26 then x = 21, y = 5.

Let k = -27 then x = 17, y = 10.

Let k = -28 then x = 13, y = 15.

Let k = -29 then x = 9, y = 20.

Let k = -30 then x = 5, y = 25.

Let k = -31 then x = 1, y = 30.

Thus the options of  (x,y  that satisfy the given equation are:

{ (25,0), (21,5), (17,10), (13, 15), (9, 20), (5, 25), (1,30)}

Q. When Mrs.Brown cashed her cheque, the absent minded teller gave her as many cents as she should have dollars, and as many dollars as she should have cents. Equally absent minded Mrs, Brown left with the cash without noticing the discrepancy. It was only after she spent 5 cents that she noticed now she had twice as much money as she should. What was the amount of her cheque?

Solution

Let x be the number of dollars Mrs Brown should have received and y be the number of cents she should have received.

Then 2(100x + y) = 100y + x - 5

Note double original amount without spending a nickel.

200x + 2y = 100y + x - 5

199x - 98y = -5.

5 = - 199x + 98y

Step 1: gcd(199,98) = 1. Since 1 | 5, we can continue.

Step 2: A solution is 51=-199(-33)(5) + (98)(-67)(5)

5 = -199(-165) + 98(-335).

Hence x = -165 and y = -335 is a solution to 5 = 98y - 199x.

Step 3: Let u = x + 165 and v = y + 335.

Consider that -199u + 98v = -199(x + 165) + 98(y + 335)

= -199x + 98y - [(199)(165) + (98)(335)]

Thus -199u + 98v = -199x + 98y - 5 = 0.

Step 4: In general, the solution to ax + by = 0 is x=bdk and y=-adk, kZ \ {0}, d=gcd(a,b).

Recall, gcd(199, 98) = 1.

Thus, u = 98k and v = 199k, k ∈ ℤ.

Step 5: Replace u and v.

x + 165 = 98k and y + 335 = 199k, k ∈ ℤ.

Hence x = -165 + 98k and y = -335 + 199k.

Step 6: Both x & y ≥ 0 and both x, y < 100

-165 + 98k ≥ 0, so k ≥ 1.68

-335 + 199k ≥ 0, so k ≥ 1.68

-165 + 98k < 100, 98k < 265, ∴ k < 2.70

-335 + 199k < 100, 199k < 435, ∴ k < 2.18

Since, 1.68 ≤ k < 2.18 and k ∈ ℤ, k = 2.

Thus, x = 98(2) - 165 = 31 and y = -335 + 199(2) = 63.

Thus, the cheque was for $31.63.

Q. To verify, the teller gave Mrs. Brown $63.31, she then spent 5 cents, leaving her with $63.26 which is twice the check amount  (2)($31.63)=$63.26 Let’s find gcd of 12 and 18. By factorization 12 = 22· 3and 18 = 32· 2,

Solution

Hence we can see gcd of 12 and 18 equal to 6, namely

(12, 18) = 6.(126,186) = (2, 3) = 1.

Theorem 2.1.2. Let a, b and c be integers. Then (a + cb, b) = (a, b).

Proof. Suppose that (a, b) = d and (a + cb, b) = k and we should prove that

d = k. If (a, b) = d, we can write a = dt and b = dp where t, p are any

Integers.

If (a + cb, b) = k, then a + cb = km and b = kn where m, n are any integers.

In a + cb, we should write instead of a and b,a = dt and cb = cdp then

(dt+cdp, dp) = (d(t+cp), dp) and from this equality, it is clear that the gcd

Of d(t+cp) and dp is equal to d, since d divide t+cp and p. So (a+cb, b) = d.

Hence we find d = k.

Q. Let’s consider those numbers; a = 190, b = 76, c = 38.

Solution

Then according to theorem, it must be like below;

(190 + 38 · 76, 76) = (190, 76)6(3078, 76) = (190, 76)

For be sure of the equality, we must find the (3078, 76) and (190, 76)

76 = 22· 19

190 = 2 · 5 · 19

3078 = 2 · 34· 19.

So, we see (3078, 76) = (190, 76) = 38.

If a and b integers, the linear combination of a and b is a sum of the form ax + by, where x and y are integers.

Theorem 2.1.3. Given integers a, b > 0, then d = (a, b) is the least positive

Integer that can be represented as ax + by and x, y integer numbers.

Proof. Assume that k is the smallest integer, k = ax+by. If d|a and d|b then,

d|ax+by, and also d ≤ k. k should divide a; otherwise a = uk+r, 0 < r < k

Where u, r ∈ Z; r = a − uk = a − u(ax + by) = a(1 − ux) + b(−uy), so we

Found another linear combination and r < k. It is a contradiction, because

Our assumption was k is the smallest integer which can be represented as

Ax + by. The process is same for proving that k|b.

Then, we get k ≤ (a, b) = d and k = d.

Q. a=169 and b = 13 26 = 2 · 13 169 = 13 · 13

Solution

We find (26, 169) = 13.

If we choose x = 1, y = −6, we can write the equation below

169 − 26 · 6 = 13 = (26, 169).

Theorem 2.1.4. If a, b, m and n are integers, and if c|a and c|b, then

c|(ma + nb).

Proof. If c|a and c|b, we can find e and f are integers, a = ce, b = cf. Then,

Ma + nb = mce + ncf = c(me + nf). Hence, we saw that ma + nb is a

Multiple of c. Thus, c|ma + nb.7

Q. a=16, b = 44 and c = 4 16 = 24 44 = 22 · 11.

Solution

So, 4 divides 16 and 44.

And assume that m = 6, n = −2, then

6 · 16 − 2 · 44 = 96 − 88 = 8.

And 4|8. Because 8 = 2 · 4.

Theorem 2.1.5. If a and b are positive integers, then the set of linear

Combinations of a and b is the set of integer multiplies of (a, b).

Proof. Suppose that (a, b) = c. Let’s show that every linear combination

Of a and b must also be a multiple of c. We know that (a, b) = c, then c|a

And c|b. Every linear combination of a and b is the form ma + nb and by

Theorem 2.1.4. We can see c|ma + nb, then ma + nb = ck. By Theorem

2.1.3. (a, b) = c can be represented a linear combination of a and b, there

Are integers s.t. x and y, (a, b) can be written like; (a, b) = ax + by. If we

Multiply both of sides with s, we get sc = sax + sby. Hence, we saw that

Every multiple of c is a linear combination of a and b.

Q. a = 28, b = 196 28 = 22 · 7 196 = 22· 72

Solution

Then (28, 196) = 14.

For any x, y ∈ Z, there are some k values which provide the equation 28x +

196y = 14k. If we consider the which x and y give us k = 2.

28x + 196y = 14 · 2.

If we divide both sides by 28, the equation reduced to

x + 7y = 1.

Hence, we find x = 8 and y = −1.

Definition 2.1.4. We will also define GCD for more than two integers.

Consider n integers, not all 0. The GCD is the largest number in the common

Divisors. The notation is (a1, a2, . . . , an).

6x ≡ 4 (mod 10), we solve it by first

Guessing the solution x0 = 4 by trial and error. Then the theorem tells

Us that [x0 + (10/2)t]10 for t = 0, 1 gives the complete solution set. Thus,

x = [4]10 and [9]10 is the complete solution. 2

Notice that we could write this as: x ≡ 4, 9 (mod 10). This congruence

Describes exactly the same set of integers as the union of the congruence

Classes [4]10, [9]10.

Even better: we can write the complete solution as: x ≡ 4 (mod 5). This

Single congruence describes the set of all integer solutions, as you should

Check. In other words, we have

[4]10 ∪ [9]10 = [4]5.

Q. Solve 230x ≡ 1081 (mod 12167).

Solution

We start by applying the Euclidean algorithm to compute d = gcd(230, 12167) = 23. Since d | 1081 there are solutions. The extended Euclidean algorithm gives the particular

Solution (s0, t0) = (53, 1) to the diophantine equation 230s − 12167t = 23,

And scaling by 47 = 1081/23 we get the particular solution (x0, y0) =

(2491, 47) to the diophantine equation 230x − 12167y = 1081. So x0 = 2491

Solves the original given congruence. In this case, m/d = 529. Thus, with

m = 12167, the set of residue classes

{[2491 + 529t]m : t = 0, 1, 2, . . . , 22}

Gives the complete solution set to the congruence.

Thus with m = 12167 we get solutions [a]m for a = 2491, 3020, 3549, 4078,

4607, 5136, 5665, 6194, 6723, 7252, 7781, 8310, 8839, 9368, 9897, 10426,

10955, 11484, 12013, 12542, 13071, 13600, 14129 and no others.

We can also say that (still with m = 12167) we get solutions [a]m for a =

2491, 3020, 3549, 4078, 4607, 5136, 5665, 6194, 6723, 7252, 7781, 8310, 8839,

9368, 9897, 10426, 10955, 11484, 12013, 375, 904, 1433, 1962.

This is because 12542 ≡ 375, 13071 ≡ 904, 13600 ≡ 1433, and 14129 ≡ 1962

(mod m).

When dealing with congruence classes, we can always replace any representative by another one!

Incidentally, we can also write the complete solution obtained above as a

Single congruence class mod 529. The complete solution is given by x ≡ 375

(mod 529). Again, the union of all 23 congruence classes mod m is a single

Congruence class mod m/d.

The examples suggest a simpler method to solve a linear congruence, which

Should always produce a single congruence class mod m/d (assuming d | m).

The remainder of this lectures explores this idea.

As a special case of the theorem, let me point out that if d = gcd(a, m) = 1

Then the linear congruance ax ≡ b (mod m) has a unique solution class.

In the special case gcd(a, m) = 1, we can always solve the congruence by

Finding the inverse of [a]m and then multiplying both sides of the congruence

By the inverse to obtain the unique solution. This is a satisfying idea because

It is so similar to what we do in ordinary high school algebra to solve linear

Equations.

Definition. An inverse of a mod m is any integer c such that a · c ≡ 1

(mod m). We write a

−1 mod m = c, or [a]

−1

m = [c]m for the modular

Inverse just defined, when it exists.

An inverse of a mod m exists iff gcd(a, m) = 1. Proving this is a good

Exercise.

Q. Suppose given the congruence 11x ≡ 15 (mod 20). Observe that d = gcd(11, 20) = 1. Thus 11x ≡ 15 (mod 20)

Solution

11x ≡ 15 (mod 20)

11 · 11x ≡ 11 · 15 (mod 20)

121x ≡ 165 (mod 20)

x ≡ 5 (mod 20).

This proves that x = [5]20 is the unique solution to the given congruence

11x ≡ 15 (mod 20).

So we can always solve ax ≡ b (mod m) in case gcd(a, m) = 1 simply by

Multiplying both sides by the inverse of [a]m (i.e., canceling the a factor).

Of course, to find the inverse of a in general requires the extended Euclidean

Algorithm to solve the corresponding diophantine equation as−mt = 1; then

c = s mod m will be an inverse of a mod m. It should be noted that if m is

Small enough then trial and error works pretty well to find an inverse, since

There are few possibilities to check.

In fact, the technique of multiplying by an inverse can be used to solve any

Linear congruence ax ≡ b (mod m), even when d = gcd(a, m) 6= 1.

Let us see why.

Assume that d = gcd(a, m) divides b. Solving the congruence ax ≡ b

(mod m) is equivalent to solving the diophantine equation ax − my = b.

But we can divide both sides of the equation by d to get a reduced diophantine equation

Ax − My = B where A = a d, M = md, B = bd.

The solutions to the reduced diophantine equation are exactly the same as

The solutions to the original one. Thus, solving ax ≡ b (mod m) is equivalent

To solving

Ax ≡ B (mod M).

This congruence satisfies the condition gcd(A, M) = 1, and thus can be

Solved by finding an inverse of A mod M and multiplying both sides by that

Inverse.

Q. Solve 230x ≡ 1081 (mod 12167)

Solution

Using new approach. We start by applying the Euclidean algorithm to compute d = gcd(230, 12167) = 23. Next, we reduce the congruence

To the equivalent congruence 10x ≡ 47 (mod 529) by dividing by d. We now

Have gcd(10, 529) = 1, so we can solve by multiplying by 10−1 mod 529. We

Can find the inverse by finding any solution to the diophantine equation

10x − 529y = 1 and then throwing away y. For instance, the extended

Euclidean algorithm gives (x, y) = (53, 1) so 10−1 ≡ 53 mod 529.

Multiplying the reduced congruence 10x ≡ 47 (mod 529) by the inverse 53

Gives the (unique!) solution x ≡ 53 · 47 ≡ 375 (mod 529).

You should verify for yourself that the union of the congruence classes [a]m

For a = 2491, 3020, 3549, 4078, 4607, 5136, 5665, 6194, 6723, 7252, 7781,

8310, 8839, 9368, 9897, 10426, 10955, 11484, 12013, 375, 904, 1433, 1962

(which we got before) gives exactly the same set of integers as the single

Congruence class [375]529.

Q. If m1, m2, .., mk are pairwise relatively prime positive integers, and if a1, a2, .., ak are any integers, then the simultaneous congruences x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ ak (mod mk)

Solution

To keep the notation simpler, we will assume k = 4. Note the proof is constructive, i.e., it shows us how to actually construct a solution. Our simultaneous congruences are  x ≡ a1 (mod m1), x ≡ a2 (mod m2), x ≡ a3 (mod m3), x ≡ a4 (mod m4). Our goal is to find integers w1, w2, w3, w4 such that:

Value mod m1 value mod m2 value mod m3 value mod m4

w1 1 0 0 0

w2 0 1 0 0

w3 0 0 1 0

w4 0 0 0 1

Once we have found w1, w2, w3, w4, it is easy to construct x:

x = a1w1 + a2w2 + a3w3 + a4w4. Moreover, as long as the moduli (m1, m2, m3, m4) remain the same, we can use the same w1, w2, w3, w4 with any a1, a2, a3, a4. First define:

z1 = m / m1 = m2m3m4

z2 = m / m2 = m1m3m4

z3 = m / m3 = m1m2m4

z4 = m / m4 = m1m2m3

Note that

i) z1 ≡ 0 (mod mj) for j = 2, 3, 4.

Ii) gcd(z1, m1) = 1. (If a prime p dividing m1 also divides

z1= m2m3m4, then p divides m2, m3, or m4.)

And likewise for z2, z3, z4.

Next define: y1 ≡ z1–1 (mod m1)

y2 ≡ z2–1 (mod m2) y3 ≡ z3–1 (mod m3) y4 ≡ z4 –1 (mod m4)

The inverses exist by (ii) above, and we can find them by Euclid’s

Extended algorithm. Note that

Iii) y1z1 ≡ 0 (mod mj) for j = 2, 3, 4. (Recall z1 ≡ 0 (mod mj) )

Iv) y1z1 ≡ 1 (mod m1)

And likewise for y2z2, y3z3, y4z4. Lastly define:

w1 ≡ y1z1 (mod m)

w2 ≡ y2z2 (mod m)

w3 ≡ y3z3 (mod m)

w4 ≡ y4z4 (mod m)

Q. Solve the simultaneous congruences x≡ 6 (mod 11), x ≡ 13 (mod 16), x ≡ 9 (mod 21), x ≡ 19 (mod 25).

Solution:

Since 11, 16, 21, and 25 are pairwise relatively prime, the

Chinese Remainder Theorem tells us that there is a unique solution

Modulo m, where m = 11⋅16⋅21⋅25 = 92400.

We apply the technique of the Chinese Remainder Theorem with

k = 4, m1 = 11, m2 = 16 m3 = 21, m4 = 25, a1 = 6, a2 = 13, a3 = 9, a4 = 19, to obtain the solution.

We compute

z1 =m /

m1 = m2m3m4 = 16⋅21⋅25 = 8400

z2 = m /

m2 = m1m3m4 = 11⋅21⋅25 = 5775

z3 =m /

m3 = m1m2m4 = 11⋅16⋅25 = 4400

z4 = m /

m4 = m1m3m3 = 11⋅16⋅21 = 3696

y1 ≡ z1–1 (mod m1) ≡ 8400–1 (mod 11)

≡ 7–1 (mod 11)

≡ 8 (mod 11)

y2 ≡ z2 –1 (mod m2) ≡ 5775–1 (mod 16)

≡ 15–1 (mod 16)

≡ 15 (mod 16)

y3 ≡ z3–1 (mod m3) ≡ 4400–1 (mod 21)

≡ 11–1 (mod 21)

≡ 2 (mod 21)

y4 ≡ z4 –1 (mod m4) ≡ 3696–1 (mod 25)

≡ 21–1 (mod 25)

≡ 6 (mod 25)

w1 ≡ y1z1 (mod m) ≡ 8⋅8400 (mod 92400)

≡ 67200 (mod 92400)

w2 ≡ y2z2 (mod m) ≡ 15⋅5775 (mod 92400)

≡ 86625 (mod 92400)

w3 ≡ y3z3 (mod m) ≡ 2⋅4400 (mod 92400)

≡ 8800 (mod 92400)

w4 ≡ y4z4 (mod m) ≡ 6⋅3696 (mod 92400)

≡ 22176 (mod 92400)

The solution, which is unique modulo 92400, is

X ≡

a1w1 +

a2w2 +

a3w3 +

a4w4 (mod 92400)

≡ 6⋅67200 + 13⋅86625 + 9⋅8800 + 19⋅22176 (mod 92400)

≡ 2029869 (mod 92400)

≡ 51669 (mod 92400)

Q. Find all solutions of x2 ≡ 1 (mod 144).

Solution:

144 = 16⋅9 = 24

32, and gcd(16,9) = 1.

We can replace our congruence by two simultaneous congruences:

x2 ≡ 1 (mod 16) and

x2 ≡ 1 (mod 9)

x2 ≡ 1 (mod 16) has 4 solutions:

x ≡ ±1 or ±7 (mod 16)

x2 ≡ 1 (mod 9) has 2 solutions:

x ≡ ±1 (mod 9)

There are 8 alternatives:

i)x ≡ 1 (mod 16) and x ≡ 1 (mod 9)

Ii)x ≡ 1 (mod 16) and x≡ –1 (mod 9)

Iii) x ≡ –1 (mod 16) and x ≡ 1 (mod 9)

Iv) x ≡ –1 (mod 16) and x ≡ –1 (mod 9)

v) x ≡ 7 (mod 16) and x ≡ 1 (mod 9)

Vi) x ≡ 7 (mod 16) and x ≡ –1 (mod 9)

Vii) x ≡ –7 (mod 16) and x ≡ 1 (mod 9)

Viii) x≡ –7 (mod 16) and x ≡ –1 (mod 9)

By the Chinese Remainder Theorem with

k = 2,

m1 = 16 and

m2 = 9, each

Case above has a unique solution for

x modulo 144.

We compute:

z1 = m2 = 9, z2 = m1 = 16, y1 ≡ 9–1 ≡ 9 (mod 16), y2 ≡ 16–1 ≡ 4 (mod 9),

w1 ≡ 9⋅9 = 81 (mod 144),

w2 ≡ 16⋅4 ≡ 64 (mod 144).

The 8 solutions are:

i) x ≡ 1⋅81 + 1⋅64 ≡ 145 ≡ 1 (mod 144)

Ii) x ≡ 1⋅81 + (–1)⋅64 ≡ 17 ≡ 17 (mod 144)

Iii) x ≡ (–1)⋅81 + 1⋅64 ≡ –17 ≡ –17 (mod 144)

Iv) x ≡ (–1)⋅81 + (–1)⋅64 ≡ –145 ≡ –1 (mod 144)

v) x ≡ 7⋅81 + 1⋅64 ≡ 631 ≡ 55 (mod 144)

Vi) x ≡ 7⋅81 + (–1)⋅64 ≡ 503 ≡ 71 (mod 144)

Vii) x ≡ (–7)⋅81 + 1⋅64 ≡ –503 ≡ –71 (mod 144)

Q. Solve the system

x≡1(mod 2)x≡2(mod 3)x≡3(mod 5).x≡1(mod 2)x≡2(mod 3)x≡3(mod 5).

Solution

We have N=2.3.5=30N=2.3.5=30. Also

N1=30/2=15,N2=30/3=10and  N3=30/5=6.(3.4.6)(3.4.6)N1=30/2=15,N2=30/3=10and  N3=30/5=6.

So we have to solve now 15y1≡1(mod 2)15y1≡1(mod 2). Thus

y1≡1(mod 2).(3.4.7)(3.4.7)y1≡1(mod 2).

In the same way, we find that

y2≡1(mod 3)and  y3≡1(mod 5).(3.4.8)(3.4.8)y2≡1(mod 3)and  y3≡1(mod 5).

As a result, we get

x≡1.15.1+2.10.1+3.6.1≡53≡23(mod 30).(3.4.9)

Q. Calculate 2345 mod 11 efficiently using Fermat’s Little Theorem.

Solution.

The number 2 is not divisible by the prime 11, so 210 ≡ 1 (mod 11)

By Fermat’s Little Theorem. By the division algorithm,

345 = 34 · 10 + 5.

Since 2345 = 234·10+5 = (210) 34· 25, then 2345 ≡ 134· 2 5 ≡ 1 · 32 ≡ 10 (mod 11).

Thus 2345 mod 11 = 10.

The result actually needed for RSA encryption is the following corollary to Fermat’s Little Theorem

References:

1. Thomas Koshy, Elementary Number Theory with Applications (2nd Edition), Academic Press, 2007.

2. Neville Robinns, Beginning Number Theory (2ndEdition), Narosa Publishing House Pvt. Limited, Delhi,2007.