**a be a positive integer from set {2, 3, 4, … 9999}. Show that there are exactly two positive integers in that set such that 10000 divides a*a-1.**

**Put \(n^2 -1 \) in place of 9999. How many positive integers a exists such that \(n^2 \)divides a(a-1)**

**Discussion:**

**Important Note:** If you are reading this, then please understand the full use of this discussion. A discussion typically begins with a comment from **Teacher **which contain hint for solution. After reading the first comment from teacher you should try to go back to the problem and solve it on your own. If you are unable to make any progress come back to this dialog. With each passing comment the solution unfolds. So it is more useful NOT to read the entire dialog in one shot. After reading each comment try the problem again and again. The only way to learn mathematics is by **doing** and the discussions in this blog are created to help you do exactly that.

**Teacher:** This is a clever problem. Especially the second part. For the first part can you find at least one value of a by trial and error? Use the prime factorization of 10000 and also the fact **a **and **a-1** are coprime numbers (why?)

**Student: **Sure. \(10000 = 2^4 5^4 \) . As a and a-1 are coprime (they are consecutive numbers), hence we all the 2’s must divide either a or a-1 and all the 5’s must divide the other one.

**Teacher: **Absolutely

**Student: **So one of the numbers is a multiple of 625 and by adding or subtracting 1 to it we hope to find a multiple of 16.

**Teacher: **Right! You can easily get one by trial and error. You want \(625k \pm 1 \equiv 0 \) mod 16 .

**Student: **625 works! If we subtract 1 from it we get 624 and that is a multiple of 16.

**Teacher: **Good. So 625 is one such number. Any other number?

**Student: **Should I check all multiples of 625 (and 16) and add (subtract) 1 from them. That will be tedious but will surely give the answer.

**Teacher: **That will definitely give the answer. But it will be very tedious. Instead observe that \(625 \equiv 1 \) mod 16.

**Student: **Oh! That will help. We want \(625k \pm 1 \equiv 0 \) mod 16 . Since \(625 \equiv 1 \) mod 16 , we want \(k \pm 1 \equiv 0 \) mod 16. So possible values of k are 1, 15, 17, 31 (or \(6t \pm 1 \) numbers). However if we put k = 17 , the 625*17 exceeds 9999 (hence is not from the set). So k=15 is the other choice. Hence a-1 = 9375 (625*15) and a= 9376 is the other choice.

**Teacher: **Very nice. Now lets try the second part. For starters can you tell me for what kind of **n **no such **a**will exist?

**Student: **Obviously if **n **is a prime. For if n is a prime (say **p**) then it is impossible to have two consecutive numbers from the set {2, … \(p^2 -1 \) } whose product will be divisible by \(p^2 \) (one of the two consecutive numbers needs to have 2 p’s but that is impossible because the first number with two p’s in it’s prime factorization is \(p^2 \) but we are taking numbers from the set {2 , 3, … , \(p^2 – 1 \) }

**Teacher: **Is it only primes that has this problem?

**Student: **Actually if \(n = p^k \) where p is a prime then we have this problem (that is there will be no such **a** for which **a(a-1) **is divisible by \(n^2 \) )

**Teacher: **Okay. Now let us consider numbers which have more that one prime factor. Suppose **n = xy **such that x and y are coprime and both greater than 1, We split **n **into two co-prime factors because we want \(n^2 \) to divide a(a-1) and we need \(x^2 \) to divide a (or (a-1)) and \(y^2 \) to divide the other one.

**Student: **I see. We can proceed as before. The idea is this: if we add or subtract 1 from a multiple of \(x^2 \) we need that to be divisible by \(y^2 \) given that \(gcd (x^2 , y^2 ) = 1 \) .

So \(x^2 k \pm 1 \equiv y^2 \)

I cannot think what to do from here?

**Teacher: **We are allowed to take numbers from the set {2,3 ,4 ..\(x^2 y^2 – 1 \) } , so think about the permissible values for k.

**Student: **Oh okay! So k can be 1, 2, 3, .. \(y^2 – 1 \) (if k = \(y^2 \) or more then \(x^2\times k \) will exceed \(x^2 y^2 -1 \) ) .

Now lets consider the set { \(x^2 , 2x^2 , 3x^2 , … , (y^2 -1) x^2 \) } . There are \(y^2 -1 \) terms in this set. If we reduce each term modulo \(y^2 \) we will get all the numbers \(1, 2, 3, … y^2 -1 \) (we get all residues except 0 as \(x^2 \times k \) is not divisible by \(y^2 \) for any value of k from 1, 2, … \(y^2 -1 \) as gcd \(( x^2 , y^2 ) \) = 1 .

**Teacher: **How can you say that we get \(1, 2, 3, … y^2 -1 \) as residues when we reduce{ \(x^2 , 2x^2 , 3x^2 , … , (y^2 -1) x^2 \) } modulo\(y^2 \)?

**Student: **Firstly we won’t get 0 (that I have mentioned in my argument before). Secondly we get \(y^2 -1 \) values . So if we can show that all residues that we get are distinct we are done. Suppose not.

Then \(x^2 k_1 \equiv x^2 k_2 \implies x^2 (k_1 – k_2) \equiv 0 \) mod \(y^2 \) . But this is not possible as \(x^2 \) and \(y^2 \) has no common factor and \(k_1 – k_2 \) is smaller than \(y^2 \) (hence not completely divisible by it)

Thus all residues we get are distinct.

**Teacher: **Very well. Proceed.

**Student: **So there will exactly two values of k for which the residues will be +1 and -1. Hence we will get exactly two values of **a** for that x, y split of **n**.

**Teacher: **Right! So what is the final answer.

**Student: **If **n** has **k** (> 1)prime factors then there are \(2^k \) ways to split it into two co prime parts and for each of them there are exactly two values of **a**. If n is a prime (or a power of a single prime) there are no such **a **.

## 2 Replies to “Divisibility of product of consecutive numbers (CMI 2015 solution)”