10^a+1 is prime at least twice

[MattcAnderson]

Hi again everybody,
I'm curiouse about positibe integers of the form 10^a + 1 where a is a
positive integer.

see my code.

> print("prime factorization of numbers of the form 10^a + 1");
for a to 20 do
b := 10^a+1;
c := ifactor(10^a+1);
print(b, " factors as ", c)
end do;
<begin Maple output>
"prime factorization of numbers of the form 10^a + 1"
11, " factors as ", (11)
101, " factors as ", (101)

<note 11 and 101 are prime numbers> </note>
<Maple output>
1001, " factors as ", (7) (11) (13)
10001, " factors as ", (73) (137)
100001, " factors as ", (11) (9091)
1000001, " factors as ", (101) (9901)
10000001, " factors as ", (11) (909091)
100000001, " factors as ", (17) (5882353)
1000000001, " factors as ", (7) (11) (13) (19) (52579) <one billion>
</Maple output>
<joke> Now that you know that One Billion has prime factorization of
7*11*13*19*52579, your life is complete. <smile> </joke>

<note> Another calculation shows that.
10^a + 1 is a composite number for integers 3<a<86.

The pattern seems to suggest that 10^a + 1 is always composite for integers a>3.
But a pattern does not make a theorem.
Anyone care to take the calculation furthur?

Regards,
Matt

PS Has someone else already done this calculation? Can we look this up somewhere?
Cheers,
Matt


P.S. After nearly a 5 hour calculation, and I trust my computer for
accurate results, I can say with certainty that the positive integers
of the form

10^a+1 are composite for integers 'a' with 3 <= a <= 97.

This I am sure of.

I'm sure someone else could extend the dataset.

Regards,
Matthew Charles Anderson

PPS Here is my raw Maple code

> restart*print("prime factorization of numbers of the form 10^a + 1");
for a to 1000 do
b := 10^a+1;
c := ifactor(10^a+1);
if isprime(b) then print(b, " factors as ", c) end if
end do;
<Maple outuput>
"prime factorization of numbers of the form 10^a + 1"
restart ()
11, " factors as ", (11)
101, " factors as ", (101)
Warning, computation interrupted
<check to see how far it calculated in 4.7 hours>(a checkpoint)
a
97

#interesting_mathematical_trivia

So to reiterate,
11 is prime, 101 is prime, and 10^a + 1 is not prime for a= 3,4,5,...,97.

Have a nice day.

[paulunderwood]

10^2^k+1 is a Generalized Fermat Number. There are very few Fermat Numbers that are prime. There will be fewer base 10 GFN primes is my guess.

[ATH]

All odd a>=3 is divisible by 11: a=2n+1
10²ⁿ⁺¹ + 1 = 100ⁿ * 10 + 1 = 1ⁿ * 10 + 1 = 0 (mod 11)

All a=4n+2 >=6 is divisible by 101:
10⁴ⁿ⁺² + 1 = 10000ⁿ * 100 + 1 = 1ⁿ * 100 + 1 = 0 (mod 101)

All a=8n+4 >=4 is divisible by 73:
10⁸ⁿ⁺⁴ + 1 =100000000ⁿ * 10000 + 1 = 1ⁿ * 10000 + 1 = 0 (mod 73)

There are probably several more of these.

[kar_bon]

5 hours of energy which could be saved by searching a well known database of such formats of number, see Studio Kamada for factors of 10^n+1 for n=1 to 150,000.

FactorDB also contains those factorizations already.

[charybdis]

If k is odd, then x^k+1 factorizes as (x+1)(x^(k-1)-x^(k-2)+...-x+1). Substituting 10^m for x, we see that 10^km+1 is divisible by 10^m+1 if k is odd. In other words, 10^n+1 cannot be prime if n has an odd factor greater than 1.
The only values of n for which this is not the case are powers of 2, so these are the only exponents for which it is possible for 10^n+1 to be prime. They are Generalized Fermat numbers as Paul says.

See Wilfrid Keller's page for the status of the base 10 GFNs. No primes are known apart from 11, and it is almost certain that no more exist. 10^(2^31)+1 is the smallest with unknown status.

[MattcAnderson]

Thank you for all the insightful replies.
Learning is an ongoing process.

I try to summarize

I never fully understood the term Generalized Fermat Number, until now.

I will accept the definition

a^(2^k) + 1 is defined as a Generalized Fermat Number

10^(2^k) + 1 as a Generalized Fermat Number with a=10.
see mathworld.Wolfram.com reference
https://mathworld.wolfram.com/GeneralizedFermatNumber.html



Here are some (somewhat new to me) identities that are related.

x^3 + 1 = (x+1)*(x^2 - x + 1).

x^5 + 1 = (x+1)*(x^4 - x^3 + x^2 - x + 1).

similarly with x^7 + 1 and bigger odd exponents.

If we let x=10, then we have cases when divisibility by 11 happens.

for example, as I was shown
10^3+1 = 11*91
10^5+1 = 11*9091
10^7+1 = 11*909091
10^9+1 = 11*90909091

there is a (somewhat more clear now) pattern here.
Let's call it an exercise in learning, or an exploration.

Time for a YouTube.com song
See "The Best of Johnny Nash"
https://www.youtube.com/watch?v=g_rB4v75jqU


On a personal note,
Okay, I do not have my textbooks any more, because
I have communal living. Over the years, some of my things have been stolen.
All my remaining textbooks are in my back shed,
and that is my space, only my wife has partially filled it with
toilet paper and supplies. I will find a way to continue my academic journey.

and have fun... and love life.
Matt
PS No matter what happens, it is worth it.

Here is the second part.

This is some very good learning for me.
To call out the helpful replies one by one,

ATH, you make some good points,
There are several general cases when we have divisibility by 11, 101, and 73.

These patterns are often difficult to flesh out, if you don't know about them.

'nearly hidden gems' if you will.

I looked at Studio Kamada and downloaded some of the data
also, the positive integer factorizations are worked out, and presented clearly.


Surely, I am not the first person who has considered numbers of this type.
(to be specific 10^a + 1 = S) where S is for Special number.

I looked at
https://stdkmd.net/ (Studio Kamada)
Specifically
stdkmd.net/nrr/
Then scroll to section 9.1 and look at second link
specifically
https://stdkmd.net/nrr/repunit/10001.htm
requires some scrolling
okay too many links

In this exploration, I did not need to 're-invent the wheel' but
to 'look up a reference'.

I feel enlightened about this number theory now.
However, tomorrow I will be onto other things.