Waste less time on Facebook — follow Brilliant.
×

It is a composite number!

\( x \) and \( y \) are both integers in the interval \( [2,100] \). Prove that there is always a positive integer \( n \), such that \( x^{2^{n}}+y^{2^{n}} \) is a composite number.

Note by Jessica Wang
1 year, 7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Now there is some n so that the expression becomes kp. We need to show that there exists n so that k > 1. Now there are some set of elements x^0,x^1...x^(d-1) modulo p. There are some set of elements 2^1,2^2...2^(f+1) modulo d so that f is the smallest number greater than or equal to 1 so that 2^(f+1)modulo d = (2^1)mod d. Note that n = f(g)+e, Where (2^n)mod(d) = (2^e)mod(d)=c. x^c mod p = h. This is an important observation: THE MODULUS OF x^2^n modulo p is entirely dependent on the modulus of n mod f. And similarly for y the modulus of y^2^n is entirely dependent on the modulus of n mod z. Now x^2^(fg+e)modp =h and y^2^(zw+t)modp = p - h (since for some n it is p). When f(g)+e=z(w)+t for and g and w (in the integers, left and right hand side are positive). The result is a multiple of p. Now given that this equation has a solution it has infinitely many solutions (euclidean algorithm) and so there are infinitely many values of n for which the result is a multiple of p. Now choose the smallest n so that the result is p. Choose a larger n which satisfies the linear diophantine equation. The result is greater than p but is a multiple of p and so is composite. Siddharth Iyer · 1 year, 7 months ago

Log in to reply

@Siddharth Iyer nice ! Aman Rajput · 1 year, 7 months ago

Log in to reply

@Aman Rajput My solution is not really nice though I would like to see better solutions Siddharth Iyer · 1 year, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...