The good ol' prime check

2 2014 + 100 7 4 2^{2014}+ 1007^4 Is this sum equal to a prime number?

No Not possible to tell Maybe Yes

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.

22 solutions

Sharky Kesa
Jul 13, 2014

@Joshua Ong 's solution is way better but here is something I noticed.

2 2014 = 4 ( m o d 10 ) 2^{2014} = 4 \pmod {10} and 100 7 4 = 1 ( m o d 10 ) 1007^4 = 1 \pmod {10}

4 + 1 = 5 4 + 1 = 5

Clearly, this number must be divisible by 5. Like I said, Joshua's is better.

what is this whole mod thing? Would FP1 mean I understand it or would I need higher? Fp2/3/ undergrad? this mod thing comes up lots and i dont get it.

Adam Cruikshank - 6 years, 11 months ago

Log in to reply

Modulus: The remainder after division. 17 MOD 5 = 2 because 17/5 = 3 with a remainder of 2.

Kimberly Rae - 2 years, 4 months ago

It means modulus. And I would say you should know it by now. I'm probably younger than you.

Joshua Ong - 6 years, 11 months ago

i did the same

Vasu Bansal - 6 years, 8 months ago

Well. The way I figured it out was similar. Looking at only the units digit, 7×7×7×7 units digit goes from 7 to 9 to 3 to 1. As for 2^2014, it goes from 2 to 4 to 8 to 6. So 2014 divided by 4 gives a remainder of 2, thus 4+1=5 it will be a larger number with units digit as 5 and so it will not be prime

Wellington Chen - 4 years, 9 months ago

You might want to change your latex.

Joshua Ong - 6 years, 11 months ago

Log in to reply

LOL, didn't see that.

Sharky Kesa - 6 years, 11 months ago

Log in to reply

I should blame myself for not noticing this easy method would work instead of the Sophie Germain identity.

Joshua Ong - 6 years, 11 months ago

Log in to reply

@Joshua Ong Well, essentially Sharky's solution is proving a specific case in the general solution of proving n 4 + 4 n n^4+4^n is not prime.

Daniel Liu - 6 years, 11 months ago

Log in to reply

@Daniel Liu Yes, exactly why I said Joshua's solution is better

Sharky Kesa - 6 years, 11 months ago

@Daniel Liu is it true that n^4 +4^n is not a prime for all n? Just clarify my doubt

Girish Chukka - 6 years, 11 months ago

Log in to reply

@Girish Chukka Only for positive integers n n greater than 1.

Sharky Kesa - 6 years, 11 months ago

yes, I did with the same method.

Kartik Sharma - 6 years, 11 months ago

The unit integers of this summation is 7, how can it be divisible by 5. Pls correct me if I have missed any point.

Vikas Gupta - 6 years, 11 months ago

Log in to reply

Last digit of 2^2014 is 4 and that of 1007^4 is 1 ,therefore last digit of sum is 5

Bharat Chhabra - 6 years, 11 months ago
Karthik Kannan
Jul 13, 2014

2 2014 + 100 7 4 = 100 7 4 + 4 ( 2 503 ) 4 2^{2014}+1007^{4}=1007^{4}+4(2^{503})^{4}

Now we can factorise this using the Sophie-Germain Identity:

( 100 7 2 + 2 ( 2 503 ) 2 + 2 ( 1007 ) ( 2 503 ) ) ( 100 7 2 + 2 ( 2 503 ) 2 2 ( 1007 ) ( 2 503 ) ) (1007^{2}+2(2^{503})^{2}+2(1007)(2^{503}))(1007^{2}+2(2^{503})^{2}-2(1007)(2^{503}))

Thus it is clear that the given number is not a prime.

Not necessarily; you still have to prove both factors are integers greater than 1. (Otherwise you can have something like 5 = 4 1 4 + 1 4 = ( 1 2 + 2 1 1 + 2 1 2 ) ( 1 2 2 1 1 + 2 1 2 ) 5 = 4 \cdot 1^4 + 1^4 = (1^2 + 2 \cdot 1 \cdot 1 + 2 \cdot 1^2) (1^2 - 2 \cdot 1 \cdot 1 + 2 \cdot 1^2) and thus claim 5 5 is not prime.)

Ivan Koswara - 6 years, 11 months ago

True, but that proof is obvious: 2^503 > 1007

Alija Bevrnja - 6 years, 11 months ago

Log in to reply

in the proof he mean 1007^4 not 1007

Elsarnagawe Mohamed - 6 years, 10 months ago

This is a very nice way ....I liked it

Kaustubh Pandey - 6 years, 11 months ago

you still have to prove both factors are integers greater than 1.

Gulshan Sharma - 6 years, 11 months ago

Wow nice proof! Didn't know about the Sophie-Germain identity so I used modulus.

Walter Tay - 5 years, 1 month ago

Would you please tell me detail about \color\red\Sophie- Germain Identity ?

Prokash Shakkhar - 4 years, 6 months ago

2 2014 4 m o d 5 2^{2014}\cong 4 mod 5 and 100 7 4 1 m o d 5 1007^{4}\cong 1 mod 5 thus 5 2 2014 + 100 7 4 5|2^{2014}+1007^{4}

Jerry McKenzie - 4 years, 1 month ago

This is an elegant way to prove its not a prime but we can also see that 5 is a divisor of this number

Kaustubh Pandey - 6 years, 11 months ago

to say that the given number is a prime or composite, each of the numbers in both the braces must be confirmed as primes or as composites but not be left as some big random numbers.

Akhil Sreekar - 6 years, 11 months ago

It's a prime number. Let 2^2014+1007^4 = 4^1007 + 1007^4 =x^y +y^x (x is even & y is odd) Let, 2^3 + 3^2 =17 ---prime 2^5 + 5^2 = 57---prime 2^7 +7^2 = 177---prime 4^5 + 5^4 = 4405---- prime It means Even^odd + Odd^even = prime Hence, from above 4^1007 + 1007^4 ---- is prime

Abdul Wahid - 5 years, 5 months ago

Log in to reply

Karthik's solution using the Sophie-Germain Identity shows it is composite. Your supposition that e v e n o d d + o d d e v e n = p r i m e even^{odd} + odd^{even}=prime is false. Your own example of 4 5 + 5 4 = 1649 4^5+5^4=1649 disproves your supposition because 1649 = 17 97 1649=17 \cdot 97 .

Michael O'Shaughnessy - 5 years, 5 months ago

How are 57 (3 x 19), 177 (3 x 59) and 4405 (5 x 881) prime numbers ?

Max Powers - 5 years, 5 months ago
Joshua Ong
Jul 12, 2014

Note that 2 2014 + 100 7 4 = 4 1007 + 100 7 4 2^{2014}+1007^4=4^{1007}+1007^4 . The rest is left as an exercise to the reader.

Yup n^4 + 4^n can never be a prime. An elementary application of sg identity :). Btw, most of these type questions have answers in the negative :P

EDIT- Exception for n=1

Krishna Ar - 6 years, 11 months ago

Log in to reply

Why can it never be prime?

Tim Lightfoot - 3 years, 5 months ago

Log in to reply

Sophie Germain (SG) Identity: a^4+4b^4 = a^4 + 4b^4 = (a^2 + 2b^2 + 2ab)(a^2 + 2b^2 - 2ab)

n^4+4^n is never prime. Proof: If n is even, then the sum is even and we are done. Since odd integers are in form 2k+1, we may perform the transformation: n^4+4^n = n^4 + 4^2k+1 = n^4 + 4(4^2k) = n^4 + 4(2^k)^4 Now, by Sophie-Germain, we are also done.

Roman Alexeev - 3 years, 4 months ago

Can you elaborate on the identity for our learning? Thanks.

Pierre Carrette - 3 years, 2 months ago

What is sg identity?

Anton Amirkhanov - 1 year, 8 months ago

Log in to reply

sophie germain. when you have a^4+4b^4, you factor as (a^2+2b^2+2ab)(a^2+b^2-2ab)

Rio Schillmoeller - 1 year, 4 months ago
Saurabh Pandey
Jul 16, 2014

last digit of 2^2014 is 4 and that of 1007^4 is 1. So, the last digit of the sum is 4+1=5 and a number ending with 5 can never be prime (except 5 itself).

It's very simple..both 2 and 7 repeat their last digits for every 4 powers.

So, if we divide the power of 2 by 4, the remainder is 2. So the last digit of 2^2014 = 4 And, if we divide the power of 7 by 4, the remainder is 0. So the last digit of 7^1004 = 1

So on adding 2^2014 and 7^1004, we get the last digit = 4+1 = 5 And, since every number ending with 5 is divisible by 5, Therefore 2^2014 + 7^1004 is NOT PRIME!!!

Anuj Agarwal - 6 years, 10 months ago
Kenny Lau
Jul 16, 2014

From Fermat's Little Theorem, 2 2014 2 2 = 4 (mod 5) 2^{2014}\equiv2^2=4\mbox{ (mod 5)} Also, 100 7 4 2 4 = 16 1 (mod 5) 1007^4\equiv2^4=16\equiv1\mbox{ (mod 5)} Therefore, 2 2014 + 100 7 4 0 (mod5) 2^{2014}+1007^4\equiv0\mbox{ (mod5)} Which proves its divisibility by 5, which makes it not a prime.

William Chau
Jul 24, 2014

Since

2^2014+1007^4

= (2^1007)^2+(1007^2)^2

= (2^1007+1007^2)^2-2(2^1007)(1007^2)

= (2^1007+1007^2)^2-[1007(2^504)]^2

= [2^1007+1007^2-1007(2^504)] * [2^1007+1007^2+1007(2^504)]

= [1007^2+(2^504)(2^503-1007)] * [2^1007+1007^2+1007(2^504)]

is a product of two positive integers, so it is composite.

Rajat Pathak
May 7, 2016

we can do it this way also....

last digit of 2^2014 = 4

last digit of 1007^4 = 1

addition of these two numbers would bear unit digit as 5.

hence it is definitely not a prime no.

This is the cleanest, most concise and eligant proof offered on this problem. Nice job!

James Schuller - 2 years, 4 months ago
Member Wilcox
Jul 15, 2014

Its 4^X +X^4 where X is 1007. All odd powers of 4 end in a 4. 1007 to the fourth ends in a 1. So the sum must end in a 5 and be divisible by 5.

Good solution

Linh Pham Ngoc Vien - 6 years, 11 months ago
Samya Chaudhary
Jul 16, 2014

1007^4 = (1000 + 7)^4- the final number is 1 as 7^4 = 2401 2^2014 = 4^1007. and alternatly powers come with end digits 4 and 6.. so if 4^(2n), the digit is 6 and 4^(2n+1) digit is 4, so last digit 4+1=5 hence not prime but a composite no.

2 no matter power wat also even 7 power wat always odd Even + odd =odd

Zack Yeung - 6 years, 11 months ago
Yashas Ravi
Oct 20, 2017

This problem can be approached logically. We know 2^2014 is not prime since whatever that number is would be divisible by 2. Also, 1007^4 is not prime since the resulting number is divisible by 1007. As a result, we have the sum of 2 composite numbers which is always composite.

The sum of two composites is not always a composite. Note 4+9=13

David Deng - 3 years, 7 months ago
Scrub Lord
Apr 5, 2017

2^2014 + 1007^4

= 4^1007 + 1007^4

= (4^1007 + 1) + (1007^4 -1)

Then, by lifting the exponents up:

(4^1007 + 1) + (1007^4 -1)

= (4 + 1)(4^1006 - 4^1005 + ... + 1) + (1007^2 + 1)(1007 + 1)(1007 - 1)

5 is a factor of (1007^2 + 1), because the last two digits of 1007^2 are 49.

Therefore, 5 is a factor of both terms in the expression.

K T
Mar 15, 2019

2 2014 4 1007 ( 1 ) 1007 1 ( m o d 5 ) 2^{2014}\equiv4^{1007}\equiv (-1)^{1007}\equiv -1 \pmod{5} and

100 7 4 2 4 1 ( m o d 5 ) 1007^4 \equiv 2^4\equiv 1\pmod{5}

So their sum must be a multiple of 5, hence not a prime.

DarkMind S.
Aug 29, 2016

2014 = 4 Mod 10 1007 = 7 Mod 10

2^4 + 7^4 = 6 + 9 Mod 10

15 Mod 10 = 5 !!!!

Henny Lim
Oct 17, 2015

2^2014 has the last digit of 4. 1007^4 has the last digit of 1. Both of them will be summed up to a number ending with 5. This is not possible to be a prime.

Sampad Lahiry
Aug 5, 2015

aha.. this is just the sophie germains identity.. just write 2^2014 as 4^1007

Christian Daang
Sep 16, 2014

My Proof: in that case, the general eq. is 2^(2x) + x^4

try x = 3 you'll get, 145

try x = 2 you'll get 32

try x = 4 you'll get, 512

So, it means, if x is a positive integer and it is not = to 1, always, it's a COMPOSITE #. therefore, the given eq. is COMPOSITE so, NO is the ANSWER.. :D

Magdalene Toh
Aug 1, 2014

We can use the Last Digit Pattern to solve this problem.

The last digit of 2 2014 2^{2014} is 4,

while the last digit of 100 7 4 1007^{4} is 1.

1+4 = 5, so the number is not a prime.

Parker Prathyoom
Jul 31, 2014

simple 2^4n+2(n=503 here)will have last digit 4 and 7^4 has last digit 1 1+4 = 5. if the last digit is 5 then it is divisible by 5

Kumar Sachin
Jul 27, 2014

unit digit wil be 5.so it will be definitely divisible by 5

Kaustubh Pandey
Jul 18, 2014

This number is divisible by 5 . If we divide it by 5 and see the remainder of both the power terms , they add up to 5 .......therefore its not a prime

Sourendranath Roy
Jul 16, 2014

when two non prime no. are added their solution is non prime...so the answer is non prime...:)

What about 10 + 9?

Alija Bevrnja - 6 years, 11 months ago

Not always...4+9 is a prime

veera venkata - 6 years, 10 months ago

Not always, as Veera and Alija demonstrate; however, the sum of two positive integers that have a common prime divisor, is composite.

Fred Shuman - 6 years, 10 months ago
Jitesh Mittal
Jul 16, 2014

As we can find the last digit of the term: (4+1) = 5 ( only the last digit....)

which is clearly divisible by 5

Rabin-Miller primality test with BigIntegers in Java: http://ideone.com/zaiCP6

Scape - 6 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...