[Aarav]

Originally Posted by chautauqua

problem 2:

as shown above, we have to show that n(3n-1) cannot be a square number for any integer n.

The proof has two steps:
1. GCD(n,3n-1) = 1
2. n and 3n-1 cannot be squares of integers simultaneously

1. GCD(n,3n-1) = GCD(n-1,n) (...using euclid's algo) = 1
2. let n=a^2, 3n-1=b^2; 'a' and 'b' are integers

=> 3*a^2 = b^2 + 1

consider 'b' of the form 3k, 3k+1, and 3k-1... In all of the above cases, b^2 + 1 is not divisible by 3. where as the LHS in the above equation is.
Hence prooved!

I hope the above solution makes sense...

Very good. But, was looking for an alternate approach, and I believe this is the shortest for this problem

[amar_kashyap]

Originally Posted by chautauqua

problem 2:

as shown above, we have to show that n(3n-1) cannot be a square number for any integer n.

The proof has two steps:
1. GCD(n,3n-1) = 1
2. n and 3n-1 cannot be squares of integers simultaneously

1. GCD(n,3n-1) = GCD(n-1,n) (...using euclid's algo) = 1
2. let n=a^2, 3n-1=b^2; 'a' and 'b' are integers

=> 3*a^2 = b^2 + 1

consider 'b' of the form 3k, 3k+1, and 3k-1... In all of the above cases, b^2 + 1 is not divisible by 3. where as the LHS in the above equation is.
Hence prooved!

I hope the above solution makes sense...

Certainly make sense.
Here is wht i have done.
n(3n-1) is a product of two co primes ( Note: n and 3n-1 are co prime to each other for any integer 'n'.)
If we just show tht 3n-1 is not a perfect square our job is done irrespective of whether 'n' is a perfct square or not.
Let's say, 3n-1 is a perfect sqaure

we can write 3n-1=3p or 3p+1 where 'p' is any integer ( any sqaure no can be represented as 3p or 3p+1)

ie n-p=1/3 or 2/3 which is not possible for integer values of 'n' and 'p'.
Hence the proof...


Note:Somebody please solve the DS wala (4th question) question

[adisehgal]

Here is what i have tried for the DS waala question :

If LCM(a,b)=HCF(c,d)
Then LHS is atleast Max(a,b) and RHS is maximum at Min(c,d) .
So a+b <= c+d . They are equal only when a=b=c=d. We have to find out if this is the case or not.
From (a) We cant say anything. They may or may not be equal and hence we cant comment about the inequality.
From(b) Since a+c<b+d , all of a,b,c,d are not equal . Hence the inequality holds true.

Therefore , we can obtain the solution by using the 2nd statement only.

I'll give a question also : (I hope its valid even if the above solution is incorrect )
Prob 5: What is the remainder : 3^1001 /1001 . (I have heard a solution partly but found it strange and left it- i dont know the answer for this)

[amar_kashyap]

the post deleted..

[chautauqua]

Originally Posted by amar_kashyap

We know by fermat's theorem that N^(p-1) -1 is a multiple of p if N is prime to P. In this case 1001 is prime to 3 so we can write

3^(1000) -1= 1001n where n is any integer.
ie 3^(1000)= 1001n+1
ie 3^(1001)= 3003n+3 which when divided by 1001 yields 3 as remainder.

The answer is 3

Prob 5:

1001 = 7*11*13 (not a prime!)

The solution has two steps:

1. Find the remainders when 3^1001 is divided by 7, 11 and 13 respectively. This is done by using Fermat's little theorem.

Now 3^6 = 7k + 1
=>3^1001 = 3^5 * (3^6)^166 = 243*(7k' + 1) = 7a + 5

Similarly: 3^1001 = 11b + 3 = 13c + 9

2. Now we have the remainders when 3^1001 is divided by 7,11, 13. Now use Euclid's algo to find the remainder when 3^1001 is divided by 7*11*13

Basically we have a = 7x+5 = 11y+3 = 13z+9

11a = 77x + 55....(i)
7a = 77y + 21...(ii)

8*(ii) - 5*(i) => a = 77k + 166 - 275 = 77k' + 47 ....(iii)

From (iii) we have: 13a = 1001k' + 13*47.....(iv)
and we also have 77a = 1001z + 77*9.......(v)

6*(iv) - (v) => a = 1001k'' + 78*47 - 77*9 = 1001*Q + 971

Ans: 971

Disclaimers:
I have not double checked the calculations....
There could be a shorter method too...

[amar_kashyap]

Oops..tht was a blunder from my side..

I am really sorry...urs seems to be an okay solution..will try to find out the short cut...

Plz post a new problem..

[amar_kashyap]

Here is what i have tried once more:

3^1001= 3. 3^1000= 3.(3^10)^100= 3.(59049)^100= 3.(1001.59-10)^100 when divided by 1001 will yield= 3.(10)^100= 30.(10^3)^33= 30 (1000)^33= 30.(1001-1)^33 when divided by 1001 will yield -30 as remainder. Hence the remainder is 971.

Hope it is okay this time

[chautauqua]

Originally Posted by amar_kashyap

Here is what i have tried once more:

3^1001= 3. 3^1000= 3.(3^10)^100= 3.(59049)^100= 3.(1001.59-10)^100 when divided by 1001 will yield= 3.(10)^100= 30.(10^3)^33= 30 (1000)^33= 30.(1001-1)^33 when divided by 1001 will yield -30 as remainder. Hence the remainder is 971.

Hope it is okay this time

nice solution....
u post a new one... I dont have any stock of problems...

[amar_kashyap]

Problem .6

Any positive real number x can be expressed as x= [x] + <x> where [x] is the greatest integer less than x and <x> is the fraction part. What is the only positive real number x for which <x>, [x] and x form a geometric progression?

a. (1-sqrt5)/2 b. (1+sqrt5)/2 c.(1-sqrt3)/2 d. (1+sqrt3)/2

[vijay317]

Originally Posted by amar_kashyap

Problem .6

Any positive real number x can be expressed as x= [x] + <x> where [x] is the greatest integer less than x and <x> is the fraction part. What is the only positive real number x for which <x>, [x] and x form a geometric progression?

a. (1-sqrt5)/2 b. (1+sqrt5)/2 c.(1-sqrt3)/2 d. (1+sqrt3)/2

We need positive real x..so we are left with b and d

1+sqrt3/2 = 2.732/2 = 1.366

so <x> = .366 [x] = 1 and x = 1.366

1.366 * .366 = 0.5 (app) so we have the answer as (1+sqrt5)/2

I am sure I might have made a mistake though..