$x$ is a positive integer so that $2^x$ and $x^2$ leaves same remainder when divided by $3$. There are many possible values for $x$. What will be the remainder when the sum of the first $2011$ values of $x$ is divided by $1000$?

Re: Dhaka Secondary 2011/9

Posted: Sat Jan 29, 2011 11:01 pm

by *Mahi*

This one is really tricky,here is how I tamed it-
Solution:

We know that
$2\equiv -1(mod 3)
\Rightarrow2^x\equiv (-1)^x(mod 3)$
So we can strike out the numbers divisible by $3$.
Now again the numbers which 'survive' are always like this-
$x^2\equiv 1 (mod 3)$
So we have to just sum up the first $2011$ even numbers which are not divisible by $3$ and get it $(mod 1000)$

Re: Dhaka Secondary 2011/9

Posted: Mon Jan 31, 2011 8:58 pm

by the arrivals

my approach is this
suppose (x,3)=1 where (a,b) means their gcd
by euler x^2=1 mod 3
and again (2,3)=1
so 2^(2y)=1mod 3
let x=2y
so we need to sort out all those numbers coprime to 3 .but note problem occurs with 6.but in this case PIE (principle of inclusion exclusion) perhaps paves da way

Re: Dhaka Secondary 2011/9

Posted: Sat Aug 27, 2011 12:34 am

by Shifat

Since if the values of x=2y typed then $X^2$ and $2^x$ will give the same remainder divided by 3, so, x is obviously even, for the first even number y=1, so actually the question becomes like this

(2+4+6+8+........................4020+4022)(mod 1000)=??
or $2011.2012 (mod 1000)$
$2011.2012$=
$(2000+11)(2000+12)$
(x+a)(x+b) apply and we get
$2000^2+ 23.2000+132$
or $0(mod 1000)+ 0(mod 1000)+ 132(mod 1000)$
so the answer is $132$...

Any apottis??

Re: Dhaka Secondary 2011/9

Posted: Mon Aug 29, 2011 1:13 am

by Abdul Muntakim Rafi

For, $x=6, 2^6=64$ which leaves 1 as a remainder when divided by 3.And $6^2=36$ which leaves 0 as a remainder... So how come 6 is a possible value of x?

Re: Dhaka Secondary 2011/9

Posted: Mon Aug 29, 2011 3:27 am

by Shifat

then maybe x= 2y where 2y mod 3 not equals 0 should be applied, suppose, 2,4,8,10,14,16,20........???(i am too interested in the problem, thinking randomly and making a mess please accept the apology??)

Re: Dhaka Secondary 2011/9

Posted: Mon Aug 29, 2011 4:24 am

by *Mahi*

This is not right.
$10^2 \equiv 2^{10} \equiv 1 (mod 3)$
You left many of this kind...

Re: Dhaka Secondary 2011/9

Posted: Mon Aug 29, 2011 5:19 am

by Shifat

yes I think this time it is okay, obviously it asks mod 3not equals 0 so, if x=(3n)^2 typed something then the mod will be 0, where 2^x will remain a remainder, and not any odd numbers of course..... and x^2 equiv 1 (mod3) when it is even,so the series should be(hope no more casualties) 2+4+8+10+14+16+...........??? we miss an even number after going through 2 consecutive even. so the last even number should be 2011*(3/2)=3016.5 or 3017th even number, But now, how can we sum them?? and ofcourse, if done, how can the (mod 1000) be found???

Re: Dhaka Secondary 2011/9

Posted: Mon Aug 29, 2011 1:20 pm

by Abdul Muntakim Rafi

The possible values of x are all even numbers except the multiples of 6...

Now how to find the summation of them...
we can do it easily by taking two integers at a time...
$ 2+4=6, 8+10=18, 14+16=30, .....................$
We got a new series...
It's $ 6+18+30+............. $
Any term of the series is $6(2n-1)$
The 1005th term of the series would be $6(1005*2-1) = 12054 $
So,the series is $ 6+18+30+..........................+12054$
The sum of them is $6060150$
Now not to forget,the sum of this series equal to the sum of first 2010 possible values of x.
2011th possible value of x is 2010th value $+4=6028+4=6032 $
so the sum of first 2011 values is $6066182$
so the remainder would be $182$
There might be any mistake in the calculation but I think the way is right...

Re: Dhaka Secondary 2011/9

Posted: Thu Sep 08, 2011 7:57 pm

by Shifat

Yes the answer is 182 and (before posting the solution I like to thank Mahi and rafi) .......
the series is $2+ 4+8+10+14+16+20+22+...........$... 2011 numbers
we can notice in the series the nth value is either 3n-1(n odd) or 3n-2(n even)
so the 2011 th number is (3.2011-1)= 6032= 32(mod 1000)
the series can be written like this $(2+4)+(8+10)+........... $..... 1005 pair of numbers
or $6+18+30+........$.. here "podoshonkha" n is 1005
as it is a particular series whare the common difference is 12
so the sum is after calculating $1005.6030$
$= 1005.(1005.6)$
$= 6.(1005)^2$
$= 6. ( 5 (mod 1000))^2$
$= 6. 25(mod 1000)$
$=150 (mod 1000)$
so the total remainder is $182(mod 1000)$
hope no jmore casualties.......