Xrfgtjtk

Prove that there is no integer a for which $a^2 - 3a - 19$ is divisible by 289.
Not got any clue. Please help.

Assume that $a^2 -3a -19 = 289n$ for some integers $a$, and $n$.

Then: $a^2 - 3a -19 - 289n = 0$, taking "delta"

$$Delta = b^2 - 4ac = (-3)^2 -4(1)(-19-289n) = 9 + 76 + 1156n = 85 + 1156n = 17(5 + 4times17n)$$

must be a perfect square.

Thus $17(5 + 4 times 17n)$ can be written as a product of squares of primes. Since $17$ is a prime itself, the factor $5 + 4 times 17n = 17p^2 times q^2 times ...t^2$ with $p, q, ..., t$ are primes.

But this means $5 + 4 times 17n = 0 pmod{17}$ a contradiction since it is $5 pmod{17}$.

$a^2-3a-19 = (a+7)^2-17(a+4)$. For $17^2$ to divide this, $17$ has to divide both $a+7$ and $a+4$, which is impossible.

Doing algebra with number systems is often easier than trying to do algebra with divisibility. This is one of those cases.

What you are asked to show is the same thing as showing

$$ a^2 -3a - 19 equiv 0 bmod 289 $$

has no solutions. $289$ is odd so that we can divide by $2$ — in particular, that means we can solve quadratic equations in the usual way. You can go through the exercise of completing the square if you like, but the quadratic formula works too:

$$begin{align}
a &= frac{3 + sqrt{(-3)^2 - 4 cdot (-19)}}{2} mod{289 }
\ &= frac{3 + sqrt{85}}{2} mod{289}
end{align}
$$

where each choice of square root gives a solution, and conversely, every solution comes from a choice of square root. (for general moduli, it is possible to have more than two square roots, although that can't happen for odd prime powers, such as this problem)

To compute square roots, it is usually best to work modulo the prime factors first, then lift to powers of primes, and finally use the Chinese Remainder Theorem to patch the solution together. Here, $289 = 17^2$, so we only have to do the first two steps.

So first, we need

$$ sqrt{85} = sqrt{0} = 0 mod{17}$$

Thus, if $85$ has a square root modulo $289$, it must be a multiple of 17.

However,

$$ (17c)^2 = 289c^2 = 0 mod{289} $$

therefore $85$ does not have a square root modulo $289$. Thus, there is no solution for $a$.

As $289=17^2,$ let us check the divisibility by $17$

$$a^2-3a-19equiv0pmod{289}implies a^2-3a-19equiv0pmod{17}$$

$$iff a^2-3aequiv19equiv2iff4a^2-12aequiv8pmod{17}text{ as }(4,17)=1$$

$$iff(2a-3)^2equiv0$$

$$iff 2aequiv3pmod{17}equiv20iff aequiv10text{ as }(2,17)=1$$

So, $a=17c+10$ where $c$ is some integer

$$a^2-3a-19=(17c+10)^2-3(17c+10)-19equiv51pmod{289}$$

Inspired by mercio

let us find $x,y$ such that $x-y=3,x+y=17implies x=10,y=7$

$$a^2-3a-19=(a-10)(a+7)+51$$

As $51$ is divisible by $17,$ so must be $(a-10)(a+7)$ to make $17|(a^2-3a-19)$

Now $17|(a-10)iff 17|(a+7)$ as $(a+7)-(a-10)=17$

So, $17^2|(a-10)(a+7),$ but $17^2not|51$

Generalization:

Let us find integer $x,y$ such that

$displaystyle x-y=-3$(the coefficient of $a$)

and $displaystyle x+y=17c$ so that either both or none $(a+x),(a-y)$ will be divisible by $17$

$implies 2x=17c-3implies c$ must be odd $=2d+1$(say) for some integer $d$

$implies x=17d+7$ and $y=x+3=17d+10$

Now, $displaystyle (a+x)(a+y)={a+(17d+7)}{a-(17d+10)}=a^2-3a-(17d+7)(17d+10)$

$displaystyleimplies a^2-3a-19={a+(17d+7)}{a-(17d+10)}+(17d+7)(17d+10)-19$

$displaystyleimplies a^2-3a-19=underbrace{{a+(17d+7)}{a-(17d+10)}}_{text{terms with difference }=17}+17^2(d^2+d)+51$

Now the logic is exactly same as the one above

In the above method $d=0$