# Solvability of Systems of Diophantine Equations using Modular Reasoning

I'll be teaching a U.S. college, freshman-level, pre-proofs discrete math course (for future teachers) this semester and one of the topics I like to cover is determining if a system of (usually linear) Diophantine equations has a solution via modular reasoning.

For example: Consider the system: $$3x+5y=7$$ $$9x-7y=12$$ A quick consideration modulo 2 (or thinking about odds and evens) shows that this does not have solutions. Some examples I use in class require other moduli.

The problem I have is that I cannot find a good exposition (print, video, or web) of this topic at the students' level. Everything I find is mired in a more advanced exposition on linear Diophantine equations suitable for a proof-based Number Theory course.

Does anyone else cover this type of reasoning with this level of student? Do you know of any (print, video, or web) materials that might be helpful to share with my students?

• Could you please clarify what pre-proofs means? – J W Jan 3 '17 at 18:10
• Students in this course have only had one semester of Calculus and the course itself does not contain formal, written, definition/theorem-referencing types of proofs. It does contain a few proofs via Venn diagram and/or proofs by table of possibilities. It mainly focuses on conceptual/computation aspects of discrete systems so that students taking the follow-up "Intro to Proofs" course can focus on the proof-writing rather than simultaneously struggling with new discrete ideas. – Aeryk Jan 3 '17 at 18:47
• Not a resource, but I suggest you do a few non-linear equations as well. For example, $x^2 = 4 y - 1$ has no solutions if you view it mod 4 (or mod 8). In general try stuff where "quadratic residues" show up. – Pat Devlin Jan 4 '17 at 15:25
• This is probably supposed to be very obvious, but how does reducing mod 2 come in? So $x$ is even and $y$ is odd, so what? Where's the contradiction? All I thought of was sheer dumb brute force: compute the solution over $\mathbb{Q}$ and find that it's not an integer solution. I'm not growing up to be a number theorist, that much is apparent. – Vandermonde Jan 5 '17 at 6:34
• @Vandermonde: Egads! You're right. In my haste to give an example, I gave an incorrect one. I will modify accordingly. – Aeryk Jan 5 '17 at 20:31