2020/022) Find integers $x,y$ such that $x^3-y^3=91$

We have $x^-y-y^3 = 91$

or $(x-y) (x^2+xy+y^2) = 91= 13 * 7$

clearly $x >=y$

So factor of 91 =  1 * 91 and 7 * 13

 so we have following 4 cases

case 1:

$x-y= 1\cdots(1)$

and $x^2 + xy + y^2 =  = 91\cdots(2)$

From (1) we have $x=y+1$

putting in (2) we get $(y+1)^2 + y(y+1) + y^2 = 91$

Or $3y^2 + 3y = 90$

or $y^2+y-30=0$

or $y^2+y-30=0$

or$(y-5)(y+6)=0$

so y = 5 or -6 and x = y+ 1 gives 2 solutions

$(6,5)$ and $(-5,-6)$

case 2:

$x-y= 7\cdots(1)$

and $x^2 + xy + y^2 =  = 13\cdots(2)$

From (1) we have $x=y+7$

putting in (2) we get $(y+7)^2 + y(y+7) + y^2 = 13$

Or $3y^2 + 21y + 49 = 13$

or $3y^2+21y+36=0$

or $y^2+7y+12 =0$

or$(y+3)(y+4)=0$

so y = -3 or -4  and x = y+ 7 gives 2 solutions

$(4,-3)$ and $(3,-4)$

 

case 3:

$x-y= 13\cdots(1)$

and $x^2 + xy + y^2 =  = 7\cdots(2)$

From (1) we have $x=y+13$

putting in (2) we get $(y+13)^2 + y(y+13) + y^2 = 7$

Or $3y^2 + 39y + 169 = 7$

or $3y^2+39y+162=0$

or $y^2+13y+54 =0$

This does not have integer solution

case 4:

$x-y= 91 \cdots(1)$

and $x^2 + xy + y^2 =  = 1\cdots(2)$

From (1) we have $x=y+91$

putting in (2) we get $(y+91)^2 + y(y+91) + y^2 = 1$

Or $3y^2 + 273y + 8281 = 1$

or $3y^2+ 273y+ 8280=0$

or $y^2+91y+ 2760 =0$

ad $91^2-8 * 2760 < 0$ this does not have any real solution

This does not have integer solution

So solution sets are  $(6,5),(-5,-6),(4,-3),(3,-4)$

Short cut solution:(can be applied for objective question)

we need to find the limit of x and y

let is take the difference of $(x+1)^3 and $x^3$ this keeps on increasing when x increases for positive x

and when decreases for -ve x .

so we can bound x between -5 and 6 as $7^3-6^3 > 91$

by putting the value of x from -5 to 6 we can find the value of y as well and solution pair as above 

2011/014) Proof of existence of infinite prime numbers.

There are infininite number of prime numbers and there are a couple of proofs these are in the linked list below

http://primes.utm.edu/notes/proofs/infinite/index.html

I propose a proof that is simpler

If I prove that if for any n there is a prime > n then I am through

Let us consider n!+1

This does not have any factor from 2 to n and hence it is a prime or in case it is not a prime then prime factor > n.

So for any n there is a prime number> n

Hence proved

2011/012) To construct an AP of integers so that 3 successive elements are perfect squares.

It is proved that we cannot have an AP whose 4 successive terms are in perfect squares
But does there exist an AP whose 3 consecutive terms are perfect squares

Solution:

Let the 3 consecutive term be a^2,b^2,c^2

As they are in AP we have
b^2-a^2 = c^2-b^2
or a^2+c^2 = 2b^2

this has a solution and we know that

if x^2 + y^2 = z^2

then (x+y)^2 + (x-y)^2 = 2(x^2+y^2) = 2z^2

so if (x,y,z) is a Pythagorean triplet the (x-y)^2 , z^2, (x+y)^2 are perfect squares and are in AP.

Or a= x-y
b = z^2
v= x+ y
for example
(3,4,5) is Pythagorean triplet so (4-3)^2, 5^2,(4+3)^2 or 1,25,49
(5,12,13) Pythagorean triplet so (12-5)^2, 13^2,(12+5)^2 or 49,169,289

Parametric form of Pythagorean triplet is
(m^2-n^2), (2mn), m^2 + n^2

So Parametric form of the required AP is

(m^2-n^2-2mn)^2,(m^2+n^2)^2,(m^2-n^2+2mn)^2

2011/011) what is the smallest prime factor of 2010! +1

As per Wilson's theorem for prime p

(p- 1)! = - 1 mod p

as as 2011 is a prime number

2010 ! = - 1 mod 2011

so 2011 is a factor of 2010 ! + 1

and as 2 to 2010 cannot divide it so smallest prime factor is 2011

2011/002) product of sum of squares is sum of squares

Prove that product of two numbers, each of which can be expressed as sum of two squares, can itself be expressed as sum of two squares.

Let 1st number be a^2+b^2 and second be c^2 + d^2
one way

(a^2+b^2)(c^2+d^2)
= (a^2c^2 + b^2 d^2 + a^2d^2 + b^2 c^2)
= (a^2c^2 + b^2 d^2 + 2 abcd + a^2d^2 + b^2 c^2- 2abcd)
= (ac+bd)^2 + ( ad - bc)^2

also
(a^2+b^2)(c^2+d^2)
= (a^2c^2 + b^2 d^2 + a^2d^2 + b^2 c^2)
= (a^2c^2 + b^2 d^2 - 2 abcd + a^2d^2 + b^2 c^2+ 2abcd)
= (ac-bd)^2 + ( ad + bc)^2

so we can do in two different ways

further we can prove using complex numbers

(a^2+b^2)(c^2+d^2) = | a + ib|^2 |c + id|^2
= | (a + ib)( c+ id)| ^ 2
= | (ac - bd) + (ad +bc) i | ^2
= (ac-bd)^2 + (ad + bc)^2

and taking (a^2+b^2)(c^2+d^2) = | a + ib|^2 |c - id|^2

we get (ac+bd)^2 + (ad - bc)^2

2010/065) an example of chinese remainder theorem

What would be the least total no. which give the remainder 1,2 and 3 when divided by 7,9 and 11?

1,2 and 3 when divided by 7,9 and 11?

hence
x= 1 mod 7
x= 2 mod 9
x =3 mod 11

now 7 ,9 and 11 are pair wise coprime

x = 1 a1b1 + 2 a2b2 + 3 a3b3 mod 7*9*11(or 693)


where a1 = 9*11 = 99
a2 = 7 * 11 = 77
a3 = 7 * 9 = 63

and
a1b1 = 1 mod 7
a2b2 = 1 mod 9
a3b3 = 1 mod 11

a1 = 99 so b1 = 99 mod 7 or 1 mod 7 so b1 = 1

77b2 mod 9 = 1 so 5b2 mod 9 = 1 so b2= 2 (as 5*2 = 10 mod 9)

63b3 = 1 mod 11 or 8b3 =1 mod 11 so b3 = 7 as 7 * 8 = 56 = 1 mod 11

So x = 1 * 99 * 1 + 2 * 77 * 2 + 3 * 63 * 7 mod 693 = 1730 mod 693

= 344 mod 693

So x if of the form 693n + 344 or lowest x = 344

2010/060) Proof of Bezout Identity

Bezout Identity states that

If a and b are integers (not both zero) then there exists integers u and v such that

Gcd(a,b) = au + bv

(Note: u and v are not unique

For example

au + bv = a(u-b) + b(v+a))

this can be used by backtracking the euclid’s equation to find Gcd(a,b) in terms of a b. this can be found in a number of books and is the standard process.

However this can be proved using pigeon hole principle also as below

We know that au is divisible by Gcd(a,b) so au mod b is divisible by Gcd(a,b)

Let gcd(a,b ) = k and
b / gcd(a,b) = t

Now taking an mod b( n from 1 to b/gcd(a,b)-1 that is t -1 ) there are

t-1 remainders

they are kn1, kn2, kn3, so on

there are t-1 remainders and all are divisible by k

no remainder can be zero

because na (n from 1 to t-1) cannot be a product of b.

no 2 remainder can be same if they are then difference is a multiple of b

so there has to a n such that one of the remainder is k

as all t- 1 remainders has to be different and values from 1 to n-1 so one remainder has to be 1

an = k mod b or an + bm = k

(u = n, v= m satisfy the condition)

2010/050) Prove that the last 6 digits of 7^10000 is 000001

we know 7^4 = 2401

so 7^10000 = (2401)^2500

now 2401^2500 = (2400+1)^2500

if we collect nth term it it (2500 C n) (2400)^n

for n > 2 2400^n is divisible by 10^6

so we need to look for n = 2 and n =1

n=0 gives 1 and 1-1 = 0

n = 2 => (2500C2)(2400)^2 = 2500*1200*2400 so 10^6 is a factor
n =1 =>(2500)(2400) = 6000000 so 10^6 is a factor

so all the elements except last that is 1 is divisible by 10^6 and last element is 1

so last 6 digits are 000001 or 7^10000 mod 10^6 = 1

2010/022) What is the largest number of 0's that can occur at the end of 1^n+2^n +3^+4^n

for every positive integer n

1^n + 2^n + 3^n + 4^n

n = 1 gives 10 and hence one zero
n =2 gives 41 so zero
n =3 gives 100 so 2 zeros

and it cannot end with > 2 zeros as it can be proved in steps as below

for it to end with k zeroes it need to be divisible by 10^k that is 2^k and 5^k. If we can show that is it not divisible by 8 then we are through.

for n > = 3, 2^n and 4^n are divisible by 8

now 1^n =1 for all n
3^n = 1 mod 8 for even n and 3 mod 8 for odd n

So 1^n + 3^n = 2 mod 8 for n even and 4 mod 8 odd n

So not divisible by 8 for any n and hence it cannot have >2 zeros

so ans is 2(for n = 3)

2010/021) Prove that there is no a for which a^2-3a -19 is divisible by 289

Proof:
As a first step as we see that 289 = 17^2.

Now a^2-3a-19 = (a-10)(a+7) + 51

The 2nd term that is 51 is divisible by 17 and for the 1st term that is product to be divisible by 17 either (a-10) or (a+7) is divisible by 17. but if one of them is divisible by 17 then the 2nd one is divisible by 17.

So 1st term is divisible by 289 and 2nd one is not divisible by 289 so sum is not divisible by 289. Or the 2nd term is divisible by 17 and 1st term is not divisible by 17 so sum is not divisible by 17.

So the expression is not divisible by 289.

2010/001) Prove that (2222^5555)+(5555^2222) is divisible by 7

Prove that (2222^5555)+(5555^2222) is divisible by 7

Proof:
we know

2222 mod 7 = 3

and 5555 mod 7 = 4 or -3

so (2222^5555)+(5555^2222) mod 7

= 3^5555 + (-3)^ 2222 mod 7
= 3^5555+ 3^2222 mod 7
= 3^2222(3^3333 + 1) mod 7


as 3^2222 is not divisible by 7 so

we need to show that

3^3333 + 1 mod 7 = 0

now as 7 is prime so as per format's little theorem

3^6 mod 7 = 1

3^3333 mod 7 = 3^(3333 mod 6) mod 7
= 3^ 3 mod 7 = 27 mod 7

so 3^3333 + 1 mod 7 = 28 mod 7 = 0

hence proved