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

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

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

Log in to reply

nice !

Aman Rajput - 2 years, 5 months ago

Log in to reply

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

Siddharth Iyer - 2 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...