Stumped on another question while studying for my Number Theory final and I would like some help. The question is as follows:
Find integers a, b, c, d, e, f and positive integer n > 1 for which there is a solution in real numbers x and y for the simultaneous equations
ax + cy = e
bx + dy = f
and yet there is not a solution in integers x and y for the simultaneous congruences:
ax + cy ≡ e (mod n)
bx + dy ≡ f (mod n)
I began by trying to find integers that satisfy the first condition and when looking at the markscheme, the answer was given to be "Any value where ad - bc ≠ 0 but also IS 0 mod n (or at least relatively prime to n)"
I don't really understand how they arrived at that solution. I'd really appreciate some pointers! Thanks!
If the determinant $ad - bc \ne 0$, there is always a real solution (in fact a rational solution). But if $n$ is prime and $ad - bc \equiv 0 \mod n$, there are $e,f$ such that there is no solution mod $n$. This is because Cramer's rule works in any field.
EDIT: In slightly more detail, the classical adjoint of the matrix $A = \pmatrix{a & c\cr b & d\cr}$ is $\text{adj}(A) = \pmatrix{d & -c\cr -b & a\cr}$. It satisfies $\text{adj}(A) A = \det(A) I$. If $A \pmatrix{x\cr y\cr} = \pmatrix{e\cr f\cr}$, then $\text{adj}(A) \pmatrix{e\cr f\cr} = \det(A) \pmatrix{x\cr y\cr}$ (and this works in any commutative ring, in particular the integers mod $n$, whether $n$ is prime or not). So if $\det(A) \equiv 0 \mod n$ but $de - cf \not \equiv 0 \mod n$ or $-be + af \not \equiv 0 \mod n$, there is no solution mod $n$.