Page 1 of 2
BdMO 2017 junior/4
Posted: Sun Feb 12, 2017 11:43 pm
by Thamim Zahin
(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$.
Re: BdMO 2017 junior/4
Posted: Sun Feb 12, 2017 11:46 pm
by Thamim Zahin
And I don't know how i missed the part (b) in the actual exam. And i not posting this solution. Left for the others.
Re: BdMO 2017 junior/4
Posted: Mon Feb 13, 2017 12:12 am
by dshasan
I also messed up part(b) during actual exam. However, I was able to find an answer using brute force then.
I got $n = 730$.
Am I correct?..
Re: BdMO 2017 junior/4
Posted: Mon Feb 13, 2017 11:46 pm
by ahmedittihad
Apply crt to get $n=585$.
Re: BdMO 2017 junior/4
Posted: Fri Feb 17, 2017 1:39 am
by Thamim Zahin
By judging the 6,7,8 ..... This one is kinda hard.... Rather than 8,9.
Re: BdMO 2017 junior/4
Posted: Wed Apr 12, 2017 2:23 pm
by jayon_2
ahmedittihad wrote:Apply crt to get $n=585$.
what is crt?
Re: BdMO 2017 junior/4
Posted: Wed Apr 12, 2017 2:31 pm
by Thamim Zahin
jayon_2 wrote:ahmedittihad wrote:Apply crt to get $n=585$.
what is crt?
Chinese remainder theorem
http://s3.amazonaws.com/aops-cdn.artofp ... theory.pdf
Take a look at Page no.40 for further information.
Re: BdMO 2017 junior/4
Posted: Wed Apr 12, 2017 7:14 pm
by ahmedittihad
So basically you do different cases on the primes dividing $n^2$ or $n-1$. And these cases yield different divisibility conditions. And CRT is the method to find the smallest number that suppression every congruence in a system. Look it up. The notation might be scary but it's quite natural and intuitive.
Re: BdMO 2017 junior/4
Posted: Thu Mar 01, 2018 7:52 pm
by prottoy das
ahmedittihad can you explain how it is 585?
Re: BdMO 2017 junior/4
Posted: Sat Mar 03, 2018 4:34 pm
by prottoydas
n^3-n=n^2(n-1)
Here we have 2 cases.
Case 1:n^2 is divisible by 73 and n-1 is divisible by 27.
Now n is the form of 73k.
We get 73k-1 is congruent to 0(mod27)
Or,-(8k+1) is congruent to 0(mod27)
Or, 8k is congruent to 26 (mod27)
Or, 4k is congruent to 13 (mod27)
Or, 4k is congruent to 40 (mod27)
Or, k is congruent to 10(mod27)
So, k=27m+10 (where m=0, 1, 2, 3, ………).Taking the smallest value of m=0 gives k=10 and n=73*10=730.
Case2: n^2 is divisible by 27 and n-1 is divisible by 73.
So, k is the form of 73K+1.
We get (73K+1)^2 is congruent to 0(mod27)
Or 5329K^2+146K+1 is congruent to 0(mod27)
Or, 10 K^2+11K+1 is congruent to 0(mod27)
Middle term of it gives,(K+1)(10K+1) is congruent to 0(mod27)
If we take K+1 is congruent to 0(mod27)
We get the smallest value of K is 26.
Now
10K+1 is congruent to 0(mod27)
Or, 10K is congruent to 26(mod27)
Or, 5K is congruent to 13(mod27)
Or, 5K is congruent to 40(mod27)
Or, K is congruent to 8(mod27)
So, K=27M+8(where M=0,1,2,3,………).Taking the smallest value of M=0 gives k=8and n=73*8+1=585