Find all integers such that $2 < x < 2014$ and $2015|(x^2-x)$

Question

Find all integers, $x$, such that $2 < x < 2014$ and $2015|(x^2-x)$.

I factored it and now I know that $x > 45$ and I have found one solution so far: $(156)(155)= (2015)(12)$. It's just that I don't think I'm approaching it the right way.

I'm new to this kind of stuff and I'm just doing this for fun so any help please?

Answer 1

You need a couple of pieces of information to complete this.

First of all, a property of prime numbers: If $p$ is a prime number such that $p ~|~ ab$, then $p~|~a$ or $p~|~b$. Also $2015=5 \cdot 13\cdot 31$.

Now, if $2015~|~N$, then $5~|~N$. Since $2015~|~x(x-1)$, $5~|~x$ or $5~|~(x-1)$; thus $x\equiv0\pmod5$ or $x\equiv1\pmod5$.

Continue with the other two factors: $13~|~x(x-1)$, so $x\equiv0\pmod{13}$ or $x\equiv1\pmod{13}$. There are now four possibilities for $x$:

1. $x\equiv0\pmod5$ and $x\equiv0\pmod{13}$
2. $x\equiv0\pmod5$ and $x\equiv1\pmod{13}$
3. $x\equiv1\pmod5$ and $x\equiv0\pmod{13}$
4. $x\equiv1\pmod5$ and $x\equiv1\pmod{13}$

When you continue with the 31 factor, you will get eight possibilities.

Here's the second piece of information you need: The Chinese Remainder Theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Now, use the Chinese Remainder Theorem to find $x\mod (5\cdot13\cdot31)$ for each of the 8 cases, and find the solutions which are in the interval $[2,2013]$. (There are six of them, one of which is 156.)

Answer 2

$2015=31\cdot13\cdot5$

Now, you need each of the primes $31,13$ and $5$ to be a divisor of either $x$ or $x-1$. In other words you need the following: $x\equiv 1$ or $x\equiv 0 \bmod 5,13,31$

There are going to be $8$ possible solutions, each of them can be solved in an easy way, the only ones that are not possible are $x\equiv 0\bmod 5,13,31$ and $x\equiv1\bmod 5,13,31$ as they would give solutions $0$ and $1$ which are not permitted.

The other $6$ combinations will provide one working solution each.

I will work through one example, the others are analogous.

$x\equiv 0\bmod 5$

$x\equiv 1 \bmod 13$

$x\equiv 1\bmod 31$

write $x=5k$, now $5k\equiv 1\bmod 13$ and so $k\equiv 8\bmod 13$ (since $8$ is the inverse of $5\bmod 13$). From here $k=13j+8$ and so $x=5(13j+8)=65j+40$

Now write $65j+40\equiv 1 \bmod 31\implies 3j\equiv-39\bmod 32\implies 3j\equiv23\equiv -8\bmod 31$, multiplying by the inverse of $3\bmod 31$ which is $21\equiv-10$ yields $j\equiv80\equiv 18\bmod 31$. from here $j=31m+18$

and so $x=65(31m+18)+40=2015m+1210$.

So this combination gives $1210$ as an answer, only $5$ other combinations remain.

Answer 3

I think the following algorithm can be usefull:

1. Observe that $x^2-x=x(x-1)$. Now $x$ and $x-1$ are coprime and then, if $2015=ab$, with $(a,b)=1$ you can suppose $a|x$ and $b|x-1$
2. For every fixed couple $(a,b)$ of coprime divisors of 2015 solve by CRT the system af congruences: $x \equiv 0 \mod a$ ^ $ x \equiv 1 \mod b$. CRT gives a unique solution $\mod ab=2015$. We call its class $X$
3. Now you have just to find the representant of the class of $X$ between $2$ and $2014$, if it exist, to find an $x$ that works.

So now you have just to apllie this algorithm to the 3 possible couple of coprime divisors of 2015, and for every couple there are only two cases to examinate...