Find Primes!
Read the following statements carefully.
[ 1 ] . It is completely impossible to find a non-constant infinite arithmetic progression such that all of the terms are prime numbers.
[ 2 ] . It isn't possible to find a non-constant polynomial f ( x ) with integer coefficients such that f ( x ) is a prime number for all integer values of x .
[ 3 ] . If f ( x ) = 4 x − 1 , it is possible to find infinite values of x such that f ( x ) is a prime.
Which of these are correct?
This problem is from the set "MCQ Is Not As Easy As 1-2-3". You can see the rest of the problems here .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Are you sure about 1)? Check out "Green-Tao Theorem", recently proven. But then again, it could be argued that "an arbitrarily long progression" is not the same as "an infinite progression".
I remember looking for long sequences of primes in arithmetic progression, a while back.
Log in to reply
Yes, The Green-Tao theorem is about existence of an arbitrarily long (but finite) arithmetic progression of primes, which is completely different from a sequence of arithmetic progression of primes having infinite number of terms. The argument that I gave for (1) should be okay here.
Log in to reply
True enough, but it's an awfully moot point, this fine distinction.
I proved part 2 in this way,let f ( x ) = a n x n + . . . . . . . . . . + a 1 x + a 0 Say f ( 1 ) = a n + a n − 1 + . . . . . . . + a 0 = c f ( 1 + c ) = a n ( 1 + c ) n + a n − 1 ( 1 + c ) n − 1 + . . . . . + a 0 Expanding binomially we get , f ( 1 + c ) = c ∗ K + ( a n + . . . . . . . . + a 0 ) for some k. f ( 1 + c ) = c ∗ K + c f ( 1 + c ) = ( K + 1 ) c Clearly K + 1 > 1 and c > 1 . Hence f ( 1 + c ) is composite!
Log in to reply
Nicely done!
You can generalize this. If f ( x ) is a polynomial with integer coefficients, then f ( a + f ( a ) ) is divisible by f ( a ) .
EDIT: Wait a second! How do you know that c > 1 ? How do you know that the coefficients of f ( x ) don't add up to ± 1 ?
Log in to reply
Because c must be a prime ^_^
Log in to reply
@Eddie The Head – Oh! totally forgot about that! :)
There is only one small part that's missing. The proof isn't rigorous until you handle this.
What if f ( 1 ) = f ( 1 + c ) ? This is very much possible [and happens when K = 0 ]. Can you complete your solution by considering this?
Log in to reply
@Mursalin Habib – As you have mentioned f ( a ) ∣ f ( a + f ( a ) ) for all integers a . So if f ( a + f ( a ) ) = p ∗ f ( a ) for some integer p > 1 and then it is composite. Otherwise if p = 1 for all such f ( a ) ,then the polynomial g ( x ) = f ( x + f ( x ) ) − f ( x ) has infinitely many solutions.But a finite degree polynomial cannot have infinite roots!
Log in to reply
@Eddie The Head – Perfect!
[I'm adding this paragraph because Brilliant wants me to " provide a more complete explanation of" my "question or response before submitting a reply". Other than that this paragraph has no significant value.]
Log in to reply
@Mursalin Habib – Did u solve it the same way???
Log in to reply
@Eddie The Head – Yes [adding more characters so that Brilliant accepts it. You can't post a comment which has less than 10 characters :)]
@Mursalin Habib – As an example, if f ( x ) = x 2 − 4 x + 5 , then f ( 1 ) = c = 2 and f ( 1 + c ) = f ( 3 ) = 2 as well.
Your argument for [ 2 ] is incomplete. What if a 0 = ± 1 ?
Log in to reply
It is not difficult to modify my original argument. There must exist an integer a such that f ( a ) = ± 1 . Then using division algorithm, we can write f ( x ) = ( x − a ) Q ( x ) + K , where Q ( x ) is a polynomial with integer coefficients (check this) and K = ± 1 . Now f ( a + K ) = K ( Q ( a + K ) + 1 ) which is definitely composite.
Log in to reply
I understand. I was merely pointing it out. You can edit your solution and add your comment in there. Makes it more complete.
My argument for #1 was as follows: take an integer m relatively prime to and larger than d . Then p n is cyclic modulo m , so there is an element of { p n } divisible by m , contradiction.
Log in to reply
Clarification: By "cyclic modulo m " I mean that the inverse e = d − 1 exists modulo m , so p e ⋅ ( m − a ) = a + d ⋅ e ( m − a ) ≡ a + 1 ( m − a ) = m ≡ 0 ( m o d m ) .
Take a bow. I learnt a lot frm dis soln.Thnx.
@Abhishek Sinha : beautiful solution!
(1) If possible, suppose such an AP is p n = a + n d , n ≥ 0 , which is prime for all n . WOLOG, we may assume that a and d are positive integers. However p a = a ( 1 + d ) which is definitely not prime.
(2) If possible such a polynomial be f ( x ) = ∑ n = 0 d a n x n . where a 0 = 0 (otherwise it is a composite number for every integer). Then just note that f ( a 0 ) = a 0 × K , where K is an integer. Thus f ( a 0 ) is not a prime.
(3) Dirichlet's Theorem