Computer Science Department – Rutgers University Spring 2018
CS 205: Final Exam Question 4 – Modulus and Diophantine 16:198:205
In class and in posted notes, we consider problems like trying to find integer solutions x, y to the equation
3x + 5y = D (1)
for various values of D. Using congruences, we were able to decouple the x and y variables, determine the ‘form’ that
x and y must have, and then return to the original equation to discover how those two forms were related. Thinking
of the above equation as a line, and noting that integer solutions must fall on that line, we were able to construct a
1-dimensional parameterization in terms of an integer parameter k, such that for any integer value of k,
x = x0 + ak
y = y0 + bk,
(2)
represented an integer solution to the original equation.
1) For a given value of D, give an explicit formula for an (x0, y0) and a, b to parameterize the integer solutions to
the above. The formula should be in terms of D, and an integer parameter k.
2) Are you confident that your parameterization captures all integer solutions to 3x+5y = D? For any D? Why?
Consider now the equation:
3x + 5y + 7z = 1. (3)
3) Prove that for any integer value of z, there are integer solutions for x and y.
4) Parameterize the set of integer solutions (x, y, z) in terms of an integer z and an integer parameter k. Note,
because the above equation represents a plane in 3-D space, the solutions are two dimensional, and thus require
two parameters (in this case, z and k).
5) Are you confident that your parameterization captures all integer solutions (x, y, z)? Why?
Now consider the system of equations:
3x + 5y + 7z = 1
7x + 3y + 5z = 1.
(4)
6) Are there any integer solutions (x, y, z) that satisfy both these equations simultaneously? The intersection of
two planes is a line, so give a 1-D integer parameterization of the integer solutions to this system.
Bonus
Adapt your work here to solve for the integer solutions to:
21x + 15y + 35z = 1. (5)
What complicates the solution here, and how can you approach solving it?
1