nliuwebsite

Euler’s Totient: A Guide

Daniel Liu

June 2021

Introduction:

Euler’s totient is a function that, when given an integer n, computes the number of integers less than n that are relatively prime to n. The function is denoted by the symbol $\phi$ . Thus, $\phi(3)$ is simply 2, since the numbers less than 3 that are relatively prime to 3 are 1 and 2. Similarly, $\phi(8)$ is 4, as we see there are four integers less than 8 relatively prime to 8: 1, 3, 5, and 7. As you will see later, this function is extremely useful in number theory, especially when computing the last a digits of a given expression, such as $23^5$ . Note that Euler’s totient is synonymous with the phi function and both names will be used interchangeably throughout this guide.

Computing Values:

Calculating values for Euler’s totient turns out to be a fairly easy task- though it may become computationally burdensome for larger integers. The general formula for the function is, given a prime integer a,

$\phi(a^k)=a^k - a^{k-1}$

Remark: From this, one can derive that $\phi$ of a prime p is always p-1.

However, this formula seems to be of little use at first glance, as it is only applicable to powers of primes, such as $7^{12}$ . This renders it useless for numbers such as 35 ( $5*7$ ) whose factorizations involve more than one prime.

Luckily, there is one identity that connects the formula to all integers:

$\phi(ab)=\phi(a)*\phi(b)$

which holds for all relatively prime integers a and b.

Example 1.1: Compute $\phi(27)$ .

Since 27’s prime factorization is $3^3$ , we simply plug this value into the formula to get

$\phi(3^3)=3^3-3^{3-1}$

which equals 18.

Example 1.2: Compute $\phi(1932)$ .

Through a bit of long division and guess-and-check, we come to the conclusion that $1932 = 2^2 * 3 * 7 * 23$ . We repeat the above process to compute that $\phi(2^2)$ is equal to 2. Because 3, 7, and 23 are all prime, we can use the identity that ϕ of a prime number is equivalent to the prime number minus one: $\phi(3)=2$ , $\phi(7)=6$ , $\phi(23)=22$ . To finish out the problem, we multiply together the values of each computation to get 528.

Exercise 1.1: Compute $\phi(17)$ .

Exercise 1.2: Compute $\phi(42226)$ .

☆ Exercise 1.3: Prove the identity $\phi(ab) = \phi(a) * \phi(b)$ .

Euler’s Theorem

Admittedly, the phi function alone has little use in the real world. However, its applications allow its influence on the field of number theory to range far. Perhaps the most prominent use is in Euler’s Theorem. The theorem states that, for coprime integers a and n,

$a^{\phi(n)} \equiv 1 (mod \ n)$

Example 2.1: Find the last two digits of $37^{2042}$ .

To find the last two digits of the number, we take its value modulo 100. At first, this task seems quite daunting. How would we find that? But note that 37 and 100 are relatively prime. This means that $37^{\phi(100)} \equiv 1 (mod \ n)$ by Euler’s theorem.

We observe that $100 = 2^2 * 5^2$ , which mean $\phi(100)$ is 40. Thus, $37^{40} \equiv 1 (mod\ 100)$ . Further, $(37^{40})^{51} = 37^{2040}$ . This means that $37^{2040} \equiv 1 (mod\ 100)$ .

We now claim that $37^{2042} \equiv 37^2 (mod\ 100)$ . From here, $37^2 =1369 \equiv 69 (mod\ 100)$ . Therefore, the last two digits of $37^{2042}$ are 69.

Example 2.2: Find the last two digits of $44^{2006}$ .

The obvious solution would be to attempt to emulate our process in the previous problem. However, we quickly realize that we are unable to do that, since 44 and 2006 are not coprime.

We shall now use properties of exponents and mod to our advantage. $44^{2006} = 4^{2006} * 11^{2006}$ . Moreover, if $4^{2005} \equiv a\ (mod\ 25)$ , then $4*4^{2005}=4a\ (mod\ 4*25)$ by the property $ac \equiv bc\ (mod\ nc)$ .

Thus, we can claim that $4^{2006} \equiv 4a\ (mod\ 100)$ .

From here, we compute $4^{2005} \ (mod\ 25)$ . If we can do this, we know $4^{2006}\ (mod\ 100)$ , based on the claim above. Since 4 and 25 are relatively prime, $4^{\phi(25)} \equiv 1\ (mod\ 25) \to 4^{20} \equiv 1\ (mod\ 25)$ . Because $(4^{20}) ^{100}$ is equivalent to $4^{2000}$ , $4^{2005} \equiv 4^5 \ (mod\ 25)$ . We can easily compute $4^5$ by hand to get that $4^{2005} \equiv -1\ (mod\ 25)$ .

This means that $4^{2006} \equiv -4\ (mod\ 100)$ .

We now compute $11^{2006}\ (mod\ 100)$ . For the sake of brevity, its calculation will not be fully explained, since it is a direct application of Euler’s theorem and exactly mirrors example 2.1, but with different numbers. $11^{2006} \equiv 61\ (mod\ 100)$ .

The answer is simply $(-4)* 61 \ (mod\ 100)$ , which equals $-244\ (mod\ 100)$ . Since -300 is the closest multiple of 100 to -244 that is still less than -244, we perform $-244 - (-300)$ to arrive at our answer, 56.

Exercise 2.1: $Find\ the\ last\ two\ digits\ of\ 29^{63}$ .

Exercise 2.2: Find the last three digits of $42^{56}$ .

☆ Exercise 2.3: Let N be a positive integer, and A(N) be the sum of the digits of N. Define S(N) to be the single digit obtained by repeatedly applying the function A(N) on N (as many times as needed). Find $S(7^{7^{7^{\dots}}})$ , where there are 2021 7’s in the tower. Hint: A(N) is equivalent to N (mod 9).

☆ Exercise 2.4: Prove that $a^{\phi(n)} \equiv 1 \ (mod\ n)$ . Hint: Consider an arbitrary set A whose elements are all taken modulo m, where each element is relatively prime to m. Prove that A is identical to set B mod m, where the elements of B are found by multiplying the elements of A by a constant a.

Solving Modular Congruences: A Guide

Daniel Liu

May, 2021

Introduction

This guide attempts to serve as a step-by-step explanation on how to solve modular congruences, a topic that many may find quite confusing. Before we begin, modular congruences are simply algebraic equations, but within the world of modular arithmetic. It deals with equalities such as $3x \equiv 7 (mod\ 17)$ , and encompasses solving techniques that one would not normally use when solving regular equations.

Chinese Remainder Theorem

The Chinese Remainder Theorem, CRT for short, essentially states that given a system of $n$ equations,

$x = a_1 (mod\ m_1)$

…

$x = a_n (mod\ m_n)$

there is a unique solution for $x$ mod $M$ , where $M = m_1 \times m_2 \times \dots \times m_n$ . Frankly, the formal statement for CRT makes very little sense at the beginning. Luckily, this theorem is very conceptual in nature, and most of the time when we solve modular congruences, we never even realize we are applying it.

A conscious and discrete application of CRT is relatively trivial for competitions like Mathcounts and the AMC 10, and therefore will not be covered in this guide.

But for those who ponder its use in modular congruences, know that it, from a broad perspective, tells us that a solution actually exists for a given congruence.

Solving Modular Congruences

Now that we have a rough idea of CRT and that solving a congruence is always possible, we proceed to find out exactly how to solve one of them. Let’s start off with an easy problem:

Example 1.1: Solve $9x \equiv 36 (mod\ 11)$ .

To solve this problem, we simply divide both sides by 9 to get that $x \equiv 4 (mod\ 11)$ , and that is our answer.

An important lesson to learn here is that we can only divide by 9 because 9 and 11 are relatively prime. This is a good thing to know and remember about modular arithmetic.

We now understand the basic idea of solving modular congruences and we move to a harder problem.

Example 1.2: Solve $9x \equiv 4 (mod\ 11)$ .

For this problem, we can’t divide both sides by some constant $c$ , so we are forced to find some other method of solving. What we do here is a clever use of mod properties- we simply subtract $11x$ from the left hand side, and still retain $4 (mod\ 11)$ . on our right hand side.

Now, we are left with $-2x \equiv 4 (mod\ 11)$ .

From here, simply divide both sides by $-2$ to get that $x \equiv -2 (mod\ 11)$ .

Example 1.3: Solve $9x \equiv 4 (mod\ 11)$ .

This problem is the exact same one as example 1.2, but we will use a different way to solve it.

Instead of using mod properties that only fit the specific problem, we seek a more generalized approach.

Our intent on finding a method of solving any modular congruence, not just the ones that have convenient and unique solutions to them, leads us to the concept of multiplicative inverses.

Multiplicative inverse: Denote the multiplicative inverse of some integer $a$ as ${a^{-1}}$ . Then for some integer $n$ such that $(a, n) = 1$ ,

$a \cdot a^{-1} \equiv 1 (mod\ n)$ .

For the problem above, we see that 9 and 11 are indeed relatively prime. From here, we want to find the multiplicative inverse of 9.

We first check 11 + 1, is that divisible by 9? Nope.

What about $2 \cdot 11 + 1$ ? Again, it is not. We keep on testing values equivalent to $1 (mod\ 11)$ until we get to 45.

Is 45 equal to $1 (mod\ 11)$ ? Yup. Is it divisible by 9? It is indeed. Therefore, we have found a multiplicative inverse of $9 (mod\ 11)$ : 5, since $5 \cdot 9 = 45$ .

Now what?

Taking wisdom from the previous problem, we multiply both sides by 5, to get that $45x \equiv 20 (mod\ 11)$ . Then, we simply subtract $44x$ from the left side because it is an integer multiple of 11, and when you take away an integer multiple of $n$ from $a (mod\ n)$ , you’re still left with $a (mod\ n)$ !

Therefore, we get that $x \equiv 20 (mod\ 11)$ , also equivalent to $-2 (mod\ 11)$ , the same answer we got last time.

Exercise 1.1: Solve $2x \equiv 4 (mod\ 5)$

Exercise 1.2: Solve $2x \equiv 3 (mod\ 5$

☆Exercise 1.3: Solve $2x \equiv 4 (mod\ 8)$

As demonstrated in example 1.3, using multiplicative inverses can be extremely helpful in solving modular congruences, especially the more complex ones. But that’s only true if a multiplicative inverse can be found in the first place. How would we systematically be able to find one without guess and check?

Finding Multiplicative Inverses

Now that we have a decent idea of what a multiplicative inverse actually is, and have some sense of how to apply it, we need to create a reliable, systematic way of finding a multiplicative inverse of a modular congruence.

Let’s use example 1.3 as a model to get us started. Our goal is to find a multiple of 9 that is one greater than a multiple of 11. How would we use algebra to express this? We can use the equation $9m = 11n + 1$ , with $m$ and $n$ being integers.

But here’s the problem: how would we find solutions to that equation without guess and check?

Well let’s play with the numbers a bit to see what we can do. First off, is there anything we can factor? Not really. 9 and 11 are relatively prime, as intended, so there is nothing we can do with them.

Now we try to move things around. What if we brought the $11n$ term to the left side? Let’s see what will happen.

We get that $9m - 11n = 1$ .

Yikes. How would we solve this?

But don’t give up yet; let’s think a bit more about this. That minus sign is a bit wacky, its presence makes it difficult to even guess and check. Let’s turn it into a plus sign with some algebra:

$9m + 11n = 1$

We can do this because $n$ doesn’t have to be positive. When it’s negative, the minus becomes a plus, and at the end, all we have to do is reverse the sign of $11n$ when $n$ is negative to get a positive version.

For example, as we found earlier, $11\cdot (-4)$ in the expression $9\cdot5 + 11\cdot (-4)$ correlates to positive 44.

But back to the equation $9m + 11n = 1$ . looks kind of familiar. Hm. What might it be?

As stated earlier, $m$ and $n$ have to be integers, so we are looking for integer solutions.

Wait. Isn’t there some sort of concept that deals only with integer solutions? Yes, Diophantine equations!

We can simply find solutions using the Euclidean algorithm process taught in this handout, if solving by guess-and-check is too hard.

Now, let’s look at an example.

Example 2.1: Solve $23x \equiv 67 (mod\ 71)$ .

Clearly, we can’t really guess-and-check our way out of this one. As done previously, we look for a solution satisfying $23m = 71n + 1$ for integers $m$ and $n$ .

Following in the last example’s footsteps, we convert this equation into a diophantine equation: $23m - 71n = 1$ , which turns into $23m + 71n = 1$ since $n$ can be positive or negative.

Now we solve using the Euclidean algorithm process:

$71 = 23 \times 3 + 2$

$\to$

$23 = 2 \times 11 + 1$

$\to$

$1 = 23 - 2 \times 11$

$= 23 - 11\times (71 - 23 \times 3)$

$=34 \times 23 -11 \times 71$

All of this calculation tells us one thing: 34 and 23 are multiplicative inverses. This is because $34 \times 23 \equiv 1 (mod\ 11)$ .

Remark: Don’t get lost in the calculation. Always remember the ultimate goal and know how to interpret the final result correctly, or else confusion will very quickly arise. As we saw above, the 11 in $11 \times 71$ had little use to us, and we therefore ignored it and only paid attention to what we wanted, the 34.

Therefore, from here, we multiply both sides by 34:

$782x \equiv 2278 (mod\ 71)$

$\to$

$782x \equiv 6 (mod\ 71)$

We follow the previous example and subtract from both sides, to get that

$x \equiv 6 (mod\ 71)$

This problem took quite a bit of calculation and algebra to solve, but ultimately we have succeeded in our goal and have found a general process for solving modular congruences.

Modular Congruences: The General Method

The general solution to the congruence $a \equiv b (mod\ n)$ is as follows:

Set $a \equiv 1 (mod\ n)$ .
Turn the congruence into a diophantine equation involving $a$ and $n$ , $ap + np = 1$ .
Solve the diophantine equation (click here for more on solving diophantine equations).
Use the results to find the multiplicative inverse of $a$ .
Multiply both sides of the congruence by the multiplicative inverse, now denoted as $m$ , to get $am \equiv c (mod\ n)$ .
Subtract $a(m - 1)$ from both sides of the equation, which is an integer $n$ , to get $a \equiv c (mod\ n)$ , the solution of the problem.

The past 8 pages of this guide was dedicated to finding a general solution that, ultimately, can be summed up in 6 simple steps. So why does this matter?

It matters because it’s a very good example of how the reasoning behind one single statement in mathematics can take days, months, or even years to derive.

Now although this guide is not meant to take several years to understand, 8 pages of reasoning simplified to 6 steps teaches an important lesson: Everyone can learn a theorem and apply it. There’s nothing much to it. But what makes the difference is understanding how the theorem was arrived upon in the first place.

Handouts for Math Concepts

We want to help students learn math and improve their skills and problem-solving abilities. To do this, we have written handouts on different topics explaining techniques and tricks that can be used in math competitions. Here is the list of the handouts we have prepared.

1. Diophantine Equations: A Guide

2. Solving Modular Congruences: A Guide

3. Euler’s Totient: A Guide

Diophantine Equations: A Guide

Daniel Liu

May, 2021

Introduction

When we think of the word equation, we often think of quadratics and polynomials where the solutions are complex expressions involving square roots and $i$ . However, diophantine equations completely revise the above connotations that associate with the equal sign: they only involve integer solutions. This means that when looking at a diophantine equation, for example $x+y=1$ , would not be part of the solution set. In this guide, we will explore how to solve diophantine equations, their general solution forms, and their applications in the field of number theory.

Solving 2-Variable Diophantine Equations

Consider the equation $20x+21y=2021$ . Typically when solving, we would simply set $y$ equal to $\frac{2021-20x}{21}$ and graph the equation on a Cartesian plane. However, things get interesting when we only think about the integer solutions.

Geometrically speaking, the solution set would look like a group of individual, collinear points on a graph that can all be represented by integer coordinates. In fact, there are an infinite number of said points, and thus an infinite number of solutions.

Remark: A diophantine equation has an infinite number of solutions.

Now that we understand what a typical set of solutions to a 2-variable diophantine equation would look like, we get right into solving them.

The general protocols that one follows when solving these equations using the format $ax+by=c$ are:

Set $ax+by=1$ .
Find an integer pair $(x, y)$ that satisfies the above equation.
Turn the equation into $ax+by=c$ by multiplying $x$ and $y$ by $c$ .
Use the above solution pair to find a general form for the equation’s solutions.

Needless to say, the four steps detailed above make very little sense without application. We will now look at some examples to develop better intuition for diophantine equations.

Example 1.1: Solve the diophantine equation $x+y = 1.$

We start off with an easy equation; step one of the above procedure has already been satisfied. Now, as per step 2, we find one solution. It is fairly obvious that we have a solution at $x=1$ and $y=0$ . But is this the only solution?

There’s no need to worry about step 3 since $(1,0)$ is already a solution to the original equation (more on that in later problems). Looking at step 4, we are asked to find a general form for all solutions of the equation, meaning that the equation has more than one solution (an infinite amount to be exact, as noted previously).

So what’s another solution? Playing around with numbers a bit, we come to the conclusion that $(2, -1)$ is also a solution. What about $(3, -2)$ ? Plugging the numbers in, we see that it is indeed valid. Now some may see a pattern at this point; can you name it?

The pattern here is that each new solution can be found by adding 1 to the $x$ value and subtracting 1 from the $y$ value of the preceding solution pair. Hence, we have $(2, -1)$ derived from adding 1 to 1 and subtracting 1 from 0 in the solution pair $(1, 0)$ .

Thus far, we’ve exhibited this pattern for positive $x$ -values. Naturally, this raises the question- does this pattern work for negative $x$ -values as well? Well let’s test some values.

Remark: When unsure if a pattern holds under particular conditions, it is always a good idea to make sure by testing values.

We find a “base case” involving a negative $x$ -value to build off of by guess and check. $(-1, 2)$ is the solution pair with the largest $x$ -value that is still negative, so we can use it as our base.

Applying our previously found rule of adding to the $x$ -value and subtracting from the $y$ -value, we can quickly see that $x$ simply gets larger and larger until it becomes positive. Clearly, the above rule is quite useless. Does this mean the pattern we found is invalid for all negative $x$ ? Not necessarily.

If you’ve been reading closely, you may have already found the problem with our rule: It was formed under the pretense that $x$ gets bigger and bigger and that $y$ gets smaller and smaller. Therefore, we cannot use it to verify a case in which $x$ is set to continuously decrease.

How can we transform it to encompass the fact that $x$ decreases from our base case? One idea is to reverse our rule; that is, instead of having $x$ increase by $1$ and $y$ decreases by $1$ each time, we have $x$ decrease by $1$ and $y$ increase by $1$ .

Does it work? Well the best thing to do here is to test cases. We started off with $(-1, 2)$ . Now, we test $(-2, 3)$ . Plugging these values in, it is easy to see that the original equation holds. What about $(-3, 4)$ ? Again, it works. From here, further testing of values shows that this new rule over the domain of negative integers holds.

We’ve found a pattern now -two actually- for both positive and negative integers. Back to step 4; how do we write these patterns algebraically? More importantly, how do we summarize them as one form? For now, let’s just worry about the first pattern. It can be summarized as $(1 + n, 0 - n)$ . This is true because, instead of comparing the case at hand to the previous case, we can compare the case at hand to the base case itself. That is, instead of comparing $(3, -2)$ to $(2, -1)$ , we compare $(3, -2)$ to our base case $(1, 0)$ . From here we see that each time some integer $n$ is added to the $x$ value, that same integer $n$ is subtracted from the $y$ value. Now what about the negative case?

Here’s the part where we are saved by a bout of clever algebra: $(1 + n, 0 - n)$ includes all solutions involving a negative $x$ because $n$ doesn’t have to be positive. If $n$ is negative, it would imply the exact same rule that our rule for negative $x$ ’s establishes. Thus, we have found the solution to the diophantine equation $(x + y = 1)$ .

Example 1.2: Solve the diophantine equation $5x + 2y = 13$ .

Now that we have a better understanding of the basics of solving these equations, we jump right to a typical problem.

By step 1, we set $5x + 2y = 1$ .

Following step 2, we guess and check to find a solution for this case to use it as our base; $(-1, 3)$ works.

From here, we multiply the solution pair by 13 to get $(-13, 39)$ as step 3 instructs. Before moving on, we check to see if it still satisfies the equation: $5(-13) + 2(39) = 13$ . It is valid.

We now begin step 4. For ease of computation, we can refer to the equation $5x + 2y = 1$ to find solutions and multiply them by $13$ to satisfy our original equation. Aside from $(-1, 3)$ , $(-3, 8)$ works as well after some guess-and-check. But wait.

We notice the difference between the $x$ -coordinates of the two solutions is $-2$ , and the difference between the $y$ -coordinates is $5$ . Is this a coincidence? Our intuition gained from the previous problem tells us it might not be. But let’s test just to make sure.

$(-5, 13)$ seems to work. And so does $(-7, 18)$ .

The pattern does hold. And as the previous problem told us, the pattern will continue to hold regardless of positive or negative $x$ -values.

But what happens when we multiply everything by $13$ ? When we multiply $(-1, 3)$ and $(-3, 8)$ each by 13, the difference in $x$ -coordinates is now $-26$ and the difference in $y$ -coordinates is now $65$ .

So is this the new rule, differing by $-26$ and $65$ , or does the old rule of $-2$ and $5$ still hold?

Let’s investigate. Our original case is now $(-13, 39)$ , and $(-3, 8)$ becomes $(-39, 104)$ . To get to $(-39, 104)$ , we now subtract $26$ from the $x$ -coordinate and add $65$ to the $y$ -coordinate. What if we simply subtract $2$ from the $x$ -coordinate and add $5$ to the $y$ -coordinate? We then end up with $(-15, 44)$ . Turns out, this still works!

Thus we have a general solution now: $(-13 - 2n, 39 + 5n)$ .

Exercise 1.1: Solve the diophantine equation $x + y =5$ .

Exercise 1.2: Solve the diophantine equation $2x + 3y =9$ .

Exercise 1.3: Solve the diophantine equation $2x + 6y =28$ .

A Simplification

By now, you may be wondering why solving diophantine equations can be so tedious. Although it only technically involves 4 steps, step 4 is long and computation-heavy; easy to make errors on. So then the question becomes, is there an easier way?

The answer comes in the form of a theorem:

If $a$ and $b$ are relatively prime and $(x_0, y_0)$ is a base case of the equation, then the diophantine equation $ax + by =c$ is given by

$(x_0 + bt, y_0 - at )$

for some, not necessarily positive integer $t$ .

The proof of this theorem is actually a relatively simple one: We simply need to prove that $ax_0 + by_0 = a(x_0 + bt) + b(y_0 - at )$ . This is true because, since $ax_0 + by_0$ is already equal to $c$ , we can set the two equal to each other to prove that $a(x_0 + bt) + b(y_0 - at )$ equals $c$ as well. The remainder of this proof will not be fully detailed for the sake of brevity, but direct expansion and cancellation of terms on the right hand side can easily verify this.

Theorem Application

We now know a much simpler way to solve diophantine equations. However, our understanding of this concept is still reasonably shallow.

Example 2.1: Solve the diophantine equation $5x + 2y =13$ .

This example will be a continuation of example 1.2. This time, we will instead use the theorem to solve it.

As found in 1.2, our base case is $(-13, 39)$ . Directly using our theorem and substituting in values, our general solution is $(-13 + 2n, 39 - 5n)$ , which, because $n$ can be positive or negative, is the same thing as $(-13 - 2n, 39 + 5n)$ .

Needless to say, this theorem vastly simplifies our original 4-step process, though still retaining its structure.

Remark: This is a great example of how theorems can be useful, time-saving tools in mathematics.

Exercise 2.1: Solve the diophantine equation $x + y =5$ (using the theorem).

Exercise 2.2: Solve the diophantine equation $2x + 3y =9$ (using the theorem).

Exercise 2.3: Solve the diophantine equation $2x + 6y =28$ (using the theorem).

Exercise 2.4: Two farmers agree that pigs are worth 300 dollars and that goats are worth 210 dollars. When one farmer owes the other money, he pays the debt in pigs or goats, with “change” received in the form of goats or pigs as necessary. (For example, a 390 dollar debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way (2006 AMC 12A Problem 14).

A More Complex Method

Now what if, instead of an easy base case, we get something like $243x + 79y =1$ ? We can’t really guess-and-check our way out of this one.

The procedure for these “complex” diophantine equations is outlined as follows:

Create two separate equations, one involving $(x, y)$ , and another involving $(x_0, y_0)$
Solve the equations using algebra to obtain a general form with no explicit base solution.
Use the Euclidean algorithm to obtain a base solution.

As we have done previously, we will now use $243x+79y=1$ as an example to gain intuition on the 3-step process above.

Step one: creating two separate equations.

– $243x + 79y =1$

– $243x_0 + 79y_0 =1$

That’s all there is to it.

Step two: solving the equations for a non-specified base solution.

Subtract the equations to obtain:

$243(x - x_0) + 79(y - y_0) =0$

Move one term to the other side:

$243(x - x_0) = -79(y - y_0)$

Use algebraic manipulations on the right hand side:

$243(x - x_0) = 79(y_0 - y)$

From here, observe that, since 79 and 243 are relatively prime,

$243|(y - y_0)$ and $79|(x - x_0)$

This implies that

$y = y_0 - 243p$ and $x = x_0 + 79q$

Thus, we have the solution $(x_0 + 79q, y_0 - 243p)$ . But to complete the problem, we must find an $x_0$ and an $y_0$ . This is where the hard part comes in.

We apply the Euclidean algorithm repeatedly to get:

$243 = 79 * 3 + 6$

$79 = 6 * 13 + 1$

But then we must reverse this process:

$1 = 79 - 6 * 13$

$= 79 - 13 * (243 - 79 * 3)$

$= 40 * 79 - 13 * 243$

Thus, the general form of the solution is $(-13 + 79q, 40 - 243p)$ .

However, note that this problem is a particularly easy one due to the fact that the Euclidean algorithm portion was not very extensive. Other “complex” diophantine equations will have far more computation involved.

This way of solving diophantine equations can be confusing and tedious, and is generally not recommended unless guess-and-check is completely out of the question.

Exercise 1.1: Solve the diophantine equation $101x + 33y =1$ .

Exercise 1.2: Solve the diophantine equation $101x + 33y =26$ .

COVID-R: a COVID-19 at-home self-test tool

COVID-19 has affected everyone in the world. To help fight the pandemic, we (Rob Hageboeck and Nianjun Liu at Indiana University, Daniel Liu at Park Tudor School) developed an app called COVID-R that is a simple tool people may use to assess their chances of getting COVID-19. Powered by machine learning algorithms, COVID-R can estimate the possibility of COVID-19 infection using basic information such as age and types of symptoms. But unfortunately, Apple does not publish health-related apps by individual developers. Thus, we converted COVID-R into a web-based tool last year.

To try COVID-R, please click here. When prompted, please read the disclaimer and click “Accept & Continue”. Please find a full disclaimer here, and a simple FAQ here.

Please note the limitations of COVID-R. It is based on models that may not work very well in every situation. The data used to build the models for COVID-R were acquired in 2021, so no data about the omicron variant were available at the time. For example, loss of smell and taste is not an important predictor for potential omicron infection, but is important for other variants. As a result, if COVID-R gives a low risk score, we cannot confidently say that the likelihood of infection is low. That being said, if COVID-R gives a high risk score, your likelihood of being infected is high.

If you need to double check to ensure your health, COVID-R is here for you. Let’s hope that COVID-19 ends in 2022.

Posts

We have developed COVID-R, a COVID-19 self-test tool that allows people to assess their chances of getting COVID-19 at home. Read more…