Skip to main content
Logo image

Exercises 3.6 Exercises

Exercise Group.

For each of the following linear Diophantine equations, either find the form of a general solution, or show there are no integer solutions.














Confirm all details in Subsection 3.1.1, including which theorem applies and the case \(a=b=0\text{.}\)


Find all simultaneous integer solutions to the following system of equations. (Hint: do what you would ordinarily do in high school algebra or linear algebra! Then finish the solution as we have done.)
\begin{alignat*}{3} x \amp + y \amp + \amp z \amp = \amp 100\\ x \amp + 8y \amp + \amp 50z \amp = \amp 156 \end{alignat*}


Compute the number of positive solutions to the linear Diophantine equation \(6x+9y=c\) for various values of \(c\) and compare to the three-case analysis at the end of Subsection 3.3.2.


Explore the patterns in the positive integer solutions to \(ax+by=c\) situation in Section 3.3. For sure I want you to do this for the ones I mention there, but try some other values of \(c\) and see if you see any broader patterns!


Prove that any line \(ax+by=c\) which hits the integer lattice but \(\gcd(a,b)\neq 1\) is the same as a line \(a'x+b'y=c'\) for which \(\gcd(a',b')=1\text{,}\) and explain why that means that without loss of generality Theorem 3.1.2 doesn’t need any more explanations.


Find a primitive Pythagorean triple with at least three digits for each side.


Use Proposition 3.4.9 to prove that a Pythagorean triple triangle cannot have odd area.


Prove that 360 cannot be the area of a primitive Pythagorean triple triangle.


Find a way to prove that \(x^4+y^4=z^4\) is not possible for any three positive integers \(x,y,z\text{.}\) (Hint: use Corollary 3.4.13; this exercise needs a little cleverness.)


We already saw that if \(x,y,z\) is a primitive Pythagorean triple, then exactly one of \(x,y\) is even (divisible by 2). Assume that it’s \(y\text{,}\) and then prove that \(y\) is divisible by 4.


Under the same assumptions as in the previous problem, prove that exactly one of \(x,y,z\) is divisible by 3. (Combined with the previous exercise, this proves that every area of a Pythagorean triple triangle is divisible by 6. Is it also true that exactly one of \(x,y,z\) is divisible by 5?)


A Pythagorean triple satisfies \(x^2+y^2=z^2\text{.}\) Explore patterns for triples of positive integers which satisfy \(x^2-xy+y^2=z^2\text{.}\) If Pythagorean triples correspond to right triangles, what sort of triangles do these triples correspond to?


Find a (fairly) obvious solution to the equation \(m^n=n^m\) for \(m\neq n\text{.}\) Are there other such solutions?


Show that
\begin{equation*} \gcd(x,y)^2=\gcd(x^2,xy,y^2) \end{equation*}
which we use in Proposition 3.7.2. You can try this using the set of divisors definition of gcd, or using the definition \(\gcd(a,b,c)=\gcd(\gcd(a,b),c)\text{.}\)


Explore Bresenham’s algorithm in print or online. What is the connection to this chapter? How do non-solutions to linear Diophantine equations relate to actual solutions, in this context?


Assume you have relatively prime integers \(a,b>0\) and a positive integer \(k\text{.}\) Describe all \(k-1\) positive solutions to \(ax+by=kab\text{,}\) and use Definition 2.4.1 to find \(k\) (positive) solutions to \(ax+by=kab-1\text{.}\)


Assume \(b>a\) are odd, coprime positive integers. Show that \(\left(\frac{b^2-a^2}{2},ab,\frac{b^2+a^2}{2}\right)\) is a primitive Pythagorean triple, and that all such triples are generated this way. (See Remark 3.4.8.)


Cultures across Eurasia have variants of the ‘Problem of the Hundred Fowl’ (see among others [E.5.10, Chapter 15], [E.5.1, p. 176], and [E.5.11, Section]). This one is from Abu Kamil 14  (about 900 AD). Can you find all solutions with positive integers? What if you generalize the prices of the birds? (Finding a general solution was attempted – unsuccessfully – by Chinese mathematicians for generations.)
Suppose ducks cost five coins each, chickens one coin each, but one coin buys twenty sparrows. If you spend one hundred coins to purchase one hundred birds, how many of each did you buy?
In [E.5.3, Section 6-4] a similar example of Abu Kamil’s with five unknowns is given, which he claimed had exactly \(2676\) solutions in positive integers; today such computations are of high interest in computational geometry on polytopes.