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?

  • 1
    $\begingroup$ Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. $\endgroup$ Aug 17 '15 at 9:52

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.)

  • $\begingroup$ For some reason I thought this question would have been simpler. Much appreciation for the resources you supplied and for explaining it using modular arithmetic. $\endgroup$ Aug 17 '15 at 1:49


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.


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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.