Showing posts with label Number Theory. Show all posts
Showing posts with label Number Theory. Show all posts

Wednesday, May 7, 2014

Olympiad Problems













Find the common roots of the equation x2000+x2002+1 = 0 and x3+2x2+2x+1 = 0.
#IIT #CMI #ISI

x3+2x2+2x+1 = 0
=> x3+1+2x(x+1) = 0
=> (x+1)(x2-x+1)+2x(x+1) = 0
=> (x+1)(x2-x+1+2x) = 0
=> (x+1)(x2+x+1) =0
=> x = -1,w,w2 where 'w' is the cube root of unity
Now putting these values in the expression x2000+x2002+1 we see that w and w2 only reduce it to zero. So the common roots are w,w2


Find real x for which 1/[x] + 1/[2x] = {x} + 1/3, where [x] = greatest integer less than equal to x and {x} = x – {x}.

Let x = z + f, where z is the integer part and 0 <= f < 1
Now we have two cases (a) 0 <= f < 1/2 (b) 1/2 <= f < 1
Also note that the R.H.S of the given equation i.e., {x} + 1/3 > 0 so x has to be positive.

Case (a) 0 <= f < 1/2, [x] = z and 2x = 2z + 2f , [2x] = 2z since 0 <= 2f < 1
and {x} = x – [x] = z + f – z = f.
This reduces the equation to
1/z + 1/2z = f + 1/3 ........... (1)
=> 1/z + 1/2z >= 1/3 (Since f >= 0 )
=> 3/2z >= 1/3
=> 9 >= 2z
=> 2z – 9 <= 0
=> z = 1,2,3,4
for z = 1, {x} = f = 1 which is invalid in this case
for z = 2, using equation (1) {x} = f = 5/12 < 1/2
for z = 3, using equation (1) {x} = f = 1/6 < 1/2
for z = 4, using equation (1) {x} = f = 1/24 < 1/2
so possible values of x in this case is 2+5/12, 3+1/6 and 4+1/24
i.e., x = 29/12, 19/6 and 97/24
Case(b) Following the steps of case (a) show that in this case no solution exists.
Show that abc(a³-b³)(b³-c³)(c³-a³) is always divisible by 7 where a, b and c are non-negative integers.

Result: Cube of any integer leaves remainder 0, 1 or 6 on dividing by 7.
if any one of a,b or c is divisible by 7, then abc(a³-b³)(b³-c³)(c³-a³) is divisible by 7. So we assume that none of the numbers a,b or c is divisible by 7.
Now using the result stated above a³, b³,c³ leaves remainder 1 or 6 (due to the assumption) otherwise if 7 | or 7 | or 7 | => 7 | a or 7 | b or 7 | c ( since 7 is prime) A contradiction to the assumption.
Now by Pigeon Hole Principle two of the numbers a³, b³,c³ have the same remainder. Hence their difference is divisible by 7, thus
7 | abc(a³-b³)(b³-c³)(c³-a³) in any case.

Find the remainder when 2 is divided by 1990

Result: If p is prime & p do not divide a then ap is congruent a (modulo p) (Fermat's Theorem)
Note that 1990 = 199 X 10 and 199 is a prime.
Using Fermats theorem we have 2199 is congruent 2 (modulo 199)
=> (2199 )10 is congruent 210 (modulo 199)
=> 2 is congruent 1024 (modulo 199)
i.e 199 | 2 - 1024
Now 2 and 1024 has the same last digit, which is 4 ( try to find it for 2 ). Therefore
10 | 2 - 1024
Now g.c.d (199, 10) = 1 therefore 1990 | 2 - 1024
So the remainder is 1024
google.com, pub-6701104685381436, DIRECT, f08c47fec0942fa0