Consecutive Quest


a) Can two consecutive numbers $n$ and $n-1$ both be divisible by $3$?

b) Determine the smallest integer $n > 1$ such that $n^2(n-1)$ is divisible by $1971$. [Note: $1971 = 3^3 \times 73$]


Source: BdMO 2017 National Junior P4


Proof Based Problems  


  2 Upvotes                    0 Downvotes


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

a) 

No. For the sake of contradiction, assume that $3\mid n$ and $3\mid n-1$

So, $3\mid n-(n-1)\implies 3\mid 1$. Contradiction.


b) 

The answer is $n=585$.

$1971=3^3\cdot 73$. So, $73\mid n^2\implies73\mid n$ or $73\mid n-1$.

$27\mid n^2\implies 9\mid n$ or $9\mid n-1$.


Case 1: 

$73\mid n-1$ and $9\mid n$.

Let $n-1=k\cdot 73$.

$73\cdot k\equiv n-1 \equiv 8\pmod{9}$.

But, $73\equiv 1\pmod{9}$

So, $k\equiv 8\pmod9$. Let $k=9l+8$

But, for $l=0$, $n=585$ works.


Case 2: 

$73\mid n$ and $27\mid n-1\implies 9\mid n-1$.

Let $n=k\cdot 73$.

$73\cdot k\equiv n\equiv (n-1)+1 \equiv 1\pmod{9}$.

But, $73\equiv 1\pmod{9}$

So, $k\equiv 1\pmod9$. Let $k=9l+1$

But, for $l=0$, $n=73$ does not work. For $l>0$, $n>10\cdot 73 = 730>585$.


Case 3: $73\mid n$ and $9\mid n$.

So, $9\cdot 73\mid n\implies n\geq 657>585$


Case 4: $73\mid n-1$ and $27\mid n-1$.

So, $27\cdot 73\mid n-1\implies n>n-1\geq 1971>585$


So, the answer 585 is proved.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial