# 5. Rethinking Problems¶

In experimental science, sometimes you have to rethink your problem. Perhaps a different experiment is needed, perhaps a different model, or something else. Likewise, in experimental mathematics, sometimes it is necessary to use a different approach. We will look at one such approach today; we will turn questions about numbers into questions about geometry. Also, I know that some of you are excited to use more Sage for your computation outside of this class, so we will take a little time looking at resources.

## 5.1. Reviewing the Problem¶

Our motivational problem is the following: Given positive integers and , what numbers can be written in the form , where ?

It has already led to several related questions. That is exploration!

Is there a number for which all can be written
, but cannot be? (We called this the
*conductor*.)

If there is such a number, can we find a formula or some other means of
computing it? How *many* numbers can be written , if we
know ? Remember, you can definitely try to organize your
data. Did anyone get these results?

```
L = [[(2,3), 1, 2], [(3, 4), 5, 6], [(3,6), oo, 'None'], [(5,7), 23, 24], [(7,11), 59, 60], [(9,11), 79, 80] ]
table(L,header_row=["$(a,b)$",'Frobenius Number', 'Conductor', '# Not Writable'], frame=True)
```

Frobenius Number | Conductor | # Not Writable | |
---|---|---|---|

None | |||

Let us work out by counting the numbers that are not writable. Let’s start with , and , .

A Useful Fact

Recall that we discussed a few facts about integers earlier.

Fact: If , are integers then we can write with and integers.

Fact: In this situation, .

Here is another useful fact for our situation. Many of you already know this.

Fact: For a given , the equation has a solution in integers if and only if .

That is, you can’t even write if the greatest common divisor of and doesn’t divide . This was studied by the Greeks, known by Aryabhata in the Indian Middle Ages, and rediscovered by Bachet de Méziriac about 1600.

Implication For Us: If and have a common divisor bigger than 1, there cannot be a conductor.

We already saw an example in class. I want you to think about why this might be.

Rethinking the Problem

I can prove the facts above. But just proving things are true and using them isn’t enough. Why is it true, intuitively? I believe the right place to do this is in geometry.

```
@interact
def _(a = slider(1, 20, 1, 3), b = slider(1, 20, 1, 4), c = slider(1, 30, 1, 6), viewsize = slider(5, 30, 1, 5)):
# plot the equation of the line `y = - (a/b)*x + c/b`.
p = plot(-(a/b) * x + c/b, (x, -1, viewsize), plot_points = 200)
# integer coordiantes for the lattice
lattice_pts = [[i,j] for i in [-1..viewsize] for j in [-viewsize..viewsize]]
# plot integer lattice with pointsize set to 2 and rgbcolor set to (0, 0, 0).
plot_lattice_pts = points(lattice_pts, rgbcolor = (0, 0, 0), pointsize = 20)
# Check if gcd(a, b) divides c.
if mod(c, gcd(a, b)) == 0:
# Get integers x and y in lattice_pts that lies on the line `y = - (a/b)*x + c/b`.
# These are integers that satisfy the equation a * x + b * y = c.
line_pts = [coords for coords in lattice_pts if a * coords[0] + b * coords[1] == c]
# Check if line_pts is empty. In other words, there are no integer points x and y in lattice_pts
# that lies on the line y = - (a/b)*x + c/b or satisfies the equation a * x + b * y = c. Note that
# in general, this in effect that not mean that there are no solution since there might exist
# integer pairs which are not in lattice_pts.
if line_pts == []:
# Define an empty Graphics object.
plot_line_pts = Graphics()
else:
# plot the integer points x and y in lattice_pts that lies on the line y = - (a/b)*x + c/b or
# satisfies the equation a * x + b * y = c.
plot_line_pts = points(line_pts, rgbcolor = (0, 0, 1), pointsize = 20)
# Print sentence indicating the set of solution, (integer points) satisfying the equation.
pretty_print(html("Showing solutions to $%s\,x + %s\,y = %s$ in this viewing window" %(str(a), str(b), str(c))))
# Combine the three plot objects together.
show(p + plot_lattice_pts + plot_line_pts, figsize=[5, 5], xmin = -1, xmax = viewsize, ymin = -1, ymax = viewsize)
# If gcd(a, b) does not divide c.
else:
# Print a sentence stating the gcd(a,b) does not divide c.
pretty_print(html("The gcd of $%s$ and $%s$ is $%s$, which does not divide $%s$," %(str(a), str(b), str(gcd(a,b)), str(c))))
# Print a sentence stating that there are no integer solutions satisfying the equation
pretty_print(html("so there are no non-negative integer solutions to $%s\,x + %s\,y = %s$" %(str(a), str(b), str(c))))
# Combine plot objects.
show(p + plot_lattice_pts, figsize = [5, 5], xmin = -1, xmax = viewsize, ymin = -1, ymax = viewsize)
```

(The little gray dots in the graph above are called the integer lattice. You may treat this as a definition. There are many lattices, but only one which is basically all the intersections of for all integers . So for instance is probably visible; however, note that is not a little dot, because it doesn’t have integer values.)

Since may be thought of as a line (in fact, the line

with slope ), we now have a completely different interpretation of this very basic number theory question (the “linear Diophantine equation”). It is simply asking, “When (for what , , combinations) does the line hit this lattice? If it does, can you tell me all intersections?” If you play around with the sliders you will quickly see that things work out just as promised in the theorems.

Now let’s connect this to some of the conductor questions. Given positive integers and :

How many ways are there to write as , given ?

How many lattice points (including the axes) hit this line, given ?

How is the problem different if we only allow positive and not just nonnegative?

How does the problem change if we do not allow the axes to be included?

By the way, this second question is very closely related to an extremely applied area, integer programming.

```
@interact
def _(a = slider(1, 20, 1, 3), b = slider(1, 20, 1, 4), c = slider(1, 40, 1, 4), viewsize = slider(5, 30, 1, 5), positive_only = False):
ym = c/b + 1 # ym is the value of ymax
xm = c/a + 1 # xm is the value of xmax
# plot the equation of the line `y = - (a/b)*x + c/b`.
p = plot(-(a/b) * x + c/b, -1, xm, plot_points = 200)
# integer coordiantes for the lattice
lattice_pts = [[i,j] for i in [0..xm] for j in [0..ym]]
# plot integer lattice
plot_lattice_pts = points(lattice_pts, rgbcolor = (0, 0, 0), pointsize = 2)
# Check if gcd(a, b) divides c.
if mod(c, gcd(a, b)) == 0:
# If the parameter positive_only is True. That is, find positive x and y such that `a*x + b*y = c` holds.
if positive_only:
# Get positive integers x and y in lattice_pts that lies on the line `y = - (a/b)*x + c/b`.
# These are positive integers that satisfy the equation `a * x + b * y = c`.
line_pts = [coords for coords in lattice_pts if (coords[0] > 0) and (coords[1] > 0) and (a * coords[0] + b * coords[1] == c)]
# If the parameter positive_only is False. That is, find non-negative x and y such that `a*x + b*y = c` holds.
else:
# Get non-negative integers x and y in lattice_pts that lies on the line `y = - (a/b)*x + c/b`.
# These are non-negative integers that satisfy the equation a * x + b * y = c.
line_pts = [coords for coords in lattice_pts if (coords[0] >= 0) and (coords[1] >= 0) and (a * coords[0] + b * coords[1] == c)]
# Check if line_pts is empty. In other words, there are no non-negative integer points x and y in lattice_pts
# that lies on the line y = - (a/b)*x + c/b or satisfies the equation a * x + b * y = c. Note that in general,
# this in effect does not mean that there are no solution since there might exist integer pairs which are not
# in lattice_pts.
if len(line_pts) == 0:
# Print solutions
pretty_print(html('Solutions to $%s\,x + %s\,y = %s$:' %(str(a), str(b), str(c))))
# If the parameter positive_only is True
if positive_only:
# Print no positive solution.
pretty_print(html('No positive lattice points at all!'))
# If the parameter positive_only is False
else:
# Print sentence
pretty_print(html('No nonnegative lattice points at all!'))
# Combine the two plot objects together.
show(p + plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
else:
# plot the integer points x and y in lattice_pts that lies on the line y = - (a/b)*x + c/b or
# satisfies the equation a * x + b * y = c.
plot_line_pts = points(line_pts, rgbcolor = (0, 0, 1), pointsize = 20)
pretty_print(html('Solutions to $%s\,x + %s\,y = %s$:' %(str(a), str(b), str(c))))
# If the parameter positive_only is True
if positive_only:
# Print sentence with positive integer solutions x and y in lattice_pts.
pretty_print(html('Number of positive lattice points = ' + str(len(line_pts))))
# If the parameter positive_only is False
else:
# Print sentence with non-negative integer solutions x and y in lattice_pts.
pretty_print(html('Number of nonnegative lattice points = ' + str(len(line_pts))))
# Combine the three plot objects together.
show(p + plot_lattice_pts + plot_line_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
# If gcd(a, b) does not divide c.
else:
# Print solutions.
pretty_print(html('Solutions to $%s\,x + %s\,y = %s$:' %(str(a), str(b), str(c))))
# If the parameter positive_only is True
if positive_only:
# Print no positive integer solutions.
pretty_print(html('No positive lattice points at all!'))
else:
# Print no non-negative integer solutions.
pretty_print(html('No nonnegative lattice points at all!'))
# Combine the two plot objects together.
show(p + plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym)
```

Let’s explore this - even in cases where the conductor is not very interesting. How many such points are there in the following cases?

, , ,

, , ,

, , ,

, , ,

Again, you should be able to start exploring and experimenting. Naturally, in this case I don’t only expect you to use my graphic, which is a big challenge for you to program right now. Try instead to write your own program to explore this question.