×

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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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.

- 2 years, 5 months ago

nice !

- 2 years, 5 months ago

My solution is not really nice though I would like to see better solutions

- 2 years, 5 months ago