Maybe Prime!

True or False?

The following number can never be a prime number for any positive integer n n .

1 0 1 0 1 0 n + 1 0 1 0 n + 1 0 n 1 10^{10^{10^n}} + 10^{10^n} + 10^n - 1

True False

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.

2 solutions

Hana Wehbi
Feb 19, 2017

Let: N = 1 0 1 0 1 0 n + 1 0 1 0 n + 1 0 n 1. N = 10^{10^{10^n}} + 10^{10^n} + 10^n - 1. Write n = 2 m k n = 2^m k with m m a nonnegative integer and k k a positive odd integer. For any nonnegative integer j j , 1 0 2 m j ( 1 ) j ( m o d 1 0 2 m + 1 ) . 10^{2^m j} \equiv (-1)^j \pmod{10^{2^m} + 1}. Since 1 0 n n 2 m m + 1 10^n \geq n \geq 2^m \geq m+1 ,

1 0 n 10^n is divisible by 2 n 2^n and hence by 2 m + 1 2^{m+1} , and similarly 1 0 1 0 n 10^{10^n} is divisible by 2 1 0 n 2^{10^n} and hence by 2 m + 1 2^{m+1} . It follows that N 1 + 1 + ( 1 ) + ( 1 ) 0 ( m o d 1 0 2 m + 1 ) . N \equiv 1 + 1 + (-1) + (-1) \equiv 0 \pmod{10^{2^m} + 1}. Since N 1 0 1 0 n > 1 0 n + 1 1 0 2 m + 1 N \geq 10^{10^n} > 10^n + 1 \geq 10^{2^m} + 1 , it follows that N N is composite.

Kushal Bose
Feb 20, 2017

If we expand the terms just for imagination then then the whole expression will looks like

1000......000100.....00001...0000 1 = 1000......000100.....00001...0009 1000......000100.....00001...0000-1=1000......000100.....00001...0009 .We are not interested about the number of zeroes.This big number contains only three 1's and a single 9.So, the sum of the digits is 1 + 1 + 1 + 9 = 12 0 ( m o d 3 ) 1+1+1+9=12 \equiv 0 \pmod{3} .So, the whole expression is divisible by 3 3 .

Therefore for every n n the above expression is not a prime.

Are you sure that it contains 3 1's and single 9? What is 111000000 1 111000000 - 1 ?

In fact, if you did m o d 3 \mod 3 directly, you would see that we get 1 + 1 + 1 1 = 2 ( m o d 3 ) \equiv 1 + 1 + 1 - 1 = 2 \pmod {3} .

Calvin Lin Staff - 4 years, 3 months ago

Log in to reply

But there are at least one zero between any two 1's.And there will be three 1'sI just put n=1 and see that there are three 1's and it ends with zero

Kushal Bose - 4 years, 3 months ago

Log in to reply

Fine, let me add 0's in between those one's. What is 10010010000000 - 1 ?
Or even, what is 101010 - 1 ? How many 1's are there in this expression? Are there 3 1's?

I agree that the sum of the first 3 numbers is "there are three 1's and it ends with several zeros". I disagree that subtracting 1 will make only the last digit a 9. This is true if the previous digit is a 1 (which is the case when you put in n = 1 n=1 ), BUT then you lost that 1 and so you have 1 + 1 + 9 2 ( m o d 3 ) 1 + 1 + 9 \equiv 2 \pmod{3} .

Please read this through carefully and work it out.

Calvin Lin Staff - 4 years, 3 months ago

Log in to reply

@Calvin Lin u r right i have to think about it

Kushal Bose - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...