Sum of positive integers

Question

Find the sum of all positive integers x less than 100 for which (x^2)-81 is a multiple of 100? To do this manually would be too tedious. Also, can someone explain what the latter part of the question is saying?

Answer 1

We want $(x-9)(x+9)$ to be divisible by $100$. At least one of $x-9$ and $x+9$ must be divisible by $5$. And they cannot both be, else $(x+9)-(x-9)$ would be divisible by $5$. But $18$ is not divisible by $5$.

So one of $x-9$ and $x+9$ is divisible by $25$. That gives the possibilities $x=9$, $x=34$, $x=59$, $x=84$; also $x=16$, $x=41$, $x=66$, and $x=91$.

Note all the $x$ even cases we have listed can't work, because then the product $(x-9)(x+9)$ would be odd.

Now add up the $4$ surviving numbers. We can add them "smartly" by noting that $9$ and $91$, also $59$ and $41$, add up to $100$, so our sum is $200$.

Remark: We could have avoided making an explicit list. The above solution is a compromise between a slick but somewhat abstract approach, and a tedious full listing approach.

Answer 2

We have $\displaystyle x^2\equiv81\pmod{100}\iff \left(\frac x9\right)^2\equiv1\pmod{2^2\cdot5^2}\ \ \ \ (1)$

$$\iff\left(\frac x9\right)^2\equiv1\pmod{2^2}\ \ \ \ (2)$$ and $$\iff\left(\frac x9\right)^2\equiv1\pmod{5^2}\ \ \ \ (3)$$

Using this, $(2),(3)$ each has $2$ solutions

Using this or the famous CRT, we can show that there will be $2\cdot2=4$ in-congruent solutions $\pmod{25\cdot4}$

Now, $\displaystyle (100-y)^2=100^2-200y+y^2\equiv y^2\pmod{100}$

So, if $y_1$ is a solution of $(1),$ so will be $100-y_1$ leading to a sum $y_1+100-y_1=100$

As there are four solutions i.e., two pairs, the sum has to be $2\cdot100$

We can replace $100$ here with $p^a\cdot q^b$ where $p,q$ are primes and $a,b$ are positive integers