8
$\begingroup$

I am not at a high level in math, so I have a simple question a simple Google search cannot answer, and the other Stack Exchange questions does not either. I thought about this question after reading a creative math book. Here is the question I was doing, which I used the solutions manual in shame(Not exact wording, but same idea):

The question in the blockquotes below is not the question I am asking for answers to. Some misunderstood what I am asking. What I am asking is in the last single-sentence paragraph.

Suppose $a_2,a_3,a_4,a_5,a_6,a_7$ are integers, where $0\le a_i< i$.

$\frac 57 = \frac {a_2}{2!}+\frac {a_3}{3!}+\frac {a_4}{4!}+\frac {a_5}{5!}+\frac {a_6}{6!}+\frac {a_7}{7!}$

Find $a_2+a_3+a_4+a_5+a_6+a_7$.

The solution to this particular question requires that $a_7$ and the other variables in later steps of the algebra process to be remainders when both sides are to be divided by an integer. I am now wondering what if an equation ever comes up where the method to solve for the question above cannot work due to the variables not being able to return remainders. Thus, my question is whether it is possible to solve algebraic equations with more than two variables and most variables having constant coefficients, is not a system of equations, and the variables are assumed to be integers, and the solution is unique.

Does such a way to solve such equations in general exist? If so, please explain. What is this part of math called?

Thank you.

$\endgroup$
2
$\begingroup$

When you cannot solve a diophantine equation

The MRDP theorem shows that there is no systematic method to determine whether any given diophantine equation has a solution. So if by "solve" you include figuring out whether there is no solution, then it is absolutely impossible in general. Even if you are guaranteed that it has finitely many solutions, you still cannot systematically find all of them. The reason is that otherwise we can use such an oracle $D$ to solve the halting problem as follows.

Let $H$ be the following program on input $(P,x)$:

  Output the following program $Q$ with input $n$:

    If $n = 0$ then:

      Run $P(x)$.

      Accept.

    Reject.

Then clearly $H(P,x)$ is a program that accepts a finite RE (recursively-enumerable) set. By MRDP we can computably convert it to a diophantine equation with finitely many solutions. Now all we have to do is to ask $D$ to find all solutions, and accept $(P,x)$ iff $D$ finds one solution.

Now since $D$ is supposed to always halt, it will find a solution iff $P$ halts on $x$, and hence we have computably solved the halting problem. But that is impossible and therefore $D$ cannot exist.

In summary, even if you guarantee that a diophantine equation has at most a single solution, there is in general no systematic procedure to find if there is a solution, not to say find the solution!

When you can solve a diophantine equation

For a specific diophantine equation, one may be able to find and prove the solutions via necessarily ad-hoc methods. The above shows that we cannot do better than ad-hoc methods, although each ad-hoc method may solve a large class of diophantine equations. For example, congruence mod $n$ for some fixed $n$ can easily show the non-existence of solutions for a large class of equations. It turns out that there are equations for which there are no solutions but such that congruences will never be able to rule out all possibilities.

Another situation in which we can solve a diophantine equation is if we are told that there are at least $k$ solutions, and required to find only $k$ of them. In this case we can iterate through all possibilities until we have found $k$ solutions.

Finally of course there is the trivial case where we are told to find all solutions within some finite set.

$\endgroup$
14
$\begingroup$

Multiplying by the common denominator $7!$, we get

$$ 2520 a_2 + 840 a_3 + 210 a_4 + 42 a_5 + 7 a_6 + a_7 = 3600$$ Take this mod $7$:

$$ a_7 \equiv 2 \mod 7$$ Since $0 \le a_7 < 7$, this means $a_7 = 2$, and then (substituting this and dividing by $7$): $$ 360 a_2 + 120 a_3 + 30 a_4 + 6 a_5 + a_6 = 514$$ Taking this mod $6$: $$ a_6 \equiv 4 \mod 6$$ So $a_6 = 4$.
Continuing the process, we get $$ a_5 = 0,\ a_4 = 1,\ a_3 = 1,\ a_2 = 1 $$

$\endgroup$
  • 1
    $\begingroup$ A very nice approach! $\endgroup$ – MathMajor Jul 2 '16 at 2:28
  • 1
    $\begingroup$ Thank you for your answers to the question, but that is not the question I was asking. I was asking if a general method to solve such equations exists. Thank you for that answer though! :) $\endgroup$ – Mr. Star Jul 2 '16 at 5:46
  • 1
    $\begingroup$ Very clever solution! $\endgroup$ – user305860 Jul 2 '16 at 6:10
8
$\begingroup$

Well, if the variables can take only integer values, then you have a Diophantine equation. The field of math would be number theory.

There is no general method to solve a Diophantine equation, only for special cases (e.g. yours, which happens to be linear).

$\endgroup$
  • $\begingroup$ I've always thought diophantine equation would be just intersection of normal equation solving and a lattice that restricts the values to be integers? But dunno if that intuition is how it should be thought out... $\endgroup$ – tp1 Jul 2 '16 at 0:59
  • $\begingroup$ @tp1 It's funny that you asked about your own thoughts. No one can know if you always have thought that way, only you. $\endgroup$ – Integral Jul 2 '16 at 1:40
  • $\begingroup$ How would you know my equation is linear, since there are more than 2 variables? By the way, your answer was the only answer right now that actually answers my question. Thank you for that. I've made edits to clarify my question. $\endgroup$ – Mr. Star Jul 2 '16 at 5:58
  • 4
    $\begingroup$ @tp1 Consider something like a specific case of Fermat's Last Theorem, e.g. $x^3 + y^3 = z^3$. There are a lot of solutions to this equation over the real numbers; they make up a surface in three-dimensional space. In principle if you were to intersect that with the lattice of integer points in $\mathbb{R}^3$ you'd get all the integer solutions to $x^3 + y^3 = z^3$, but how on earth are you going to determine what that intersection is? $\endgroup$ – Daniel McLaury Jul 2 '16 at 6:01
  • $\begingroup$ @Mr. Star It is linear because it is polynomial of degree one and the coefficients are real (complex). Any equation of the form $$\sum_i ^n \lambda_i x_i = y$$ is linear, where $\lambda_i \in \mathbf{R}$ (or $\mathbf{C}$). Specifically, the equation has the properties of linearity, i.e. for $\mathbf{x},\mathbf{y} \in V$ and $a,b \in \mathbf{F}$ where $V$ is a vector space and $\mathbf{F}$ its underlying field, the mapping $f(\mathbf{x}) = \sum_i^n \lambda_i x_i$ satisfies $f(a\mathbf{x} + b\mathbf{y}) = a\sum_i^n \lambda_i x_i + b \sum_i^n\lambda_iy_i = af(\mathbf{x}) + b f(\mathbf{y}).$ $\endgroup$ – user305860 Jul 2 '16 at 6:26
1
$\begingroup$

This is equivalent to asking what values a linear function $f (x) := 1_6^T x$ can take over the intersection of the following convex polytope

$$[0,1] \times [0,2] \times [0,3] \times [0,4] \times [0,5] \times [0,6]$$

with the following hyperplane

$$\left\{ x \in \mathbb{R}^6 \,\,\bigg|\,\, \frac{x_1}{2!} + \frac{x_2}{3!} + \frac{x_3}{4!} + \frac{x_4}{5!} + \frac{x_5}{6!} + \frac{x_6}{7!} = \frac{5}{7}\right\}$$

and the integer lattice $\mathbb Z^6$. This reminds me of integer programming.

Brute-forcing in Haskell

λ filter (\(x1,x2,x3,x4,x5,x6)->x1%2+x2%6+x3%24+x4%120+x5%720+x6%5040==5%7) [ (x1,x2,x3,x4,x5,x6) | x1 <- [0,1], x2 <- [0..2], x3 <- [0..3], x4 <- [0..4], x5 <- [0..5], x6 <- [0..6] ]
[(1,1,1,0,4,2)]

we conclude that there exists only one integer point, $(1,1,1,0,4,2)$, in the intersection of the polytope and the hyperplane. Evaluating $f$ at this point, we obtain

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 9$$

$\endgroup$
  • $\begingroup$ I'm not very good at math. Sorry, but I cannot understand anything here. Can you explain it simpler? $\endgroup$ – Mr. Star Jul 2 '16 at 5:47
  • $\begingroup$ @Mr.Star Imagine a 3D cube and a plane that intersects it. Are there any points in the intersection that have integer coordinates? Read about en.wikipedia.org/wiki/Integer_programming $\endgroup$ – Rodrigo de Azevedo Jul 2 '16 at 10:48
  • $\begingroup$ You can write [0..n] instead of [0,1..n] $\endgroup$ – Christian Sievers Jul 2 '16 at 12:06
  • $\begingroup$ @ChristianSievers Fixed. $\endgroup$ – Rodrigo de Azevedo Jul 2 '16 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.