×

# 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, 2 months ago

Sort by:

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. · 1 year, 2 months ago

nice ! · 1 year, 2 months ago