Divisible by a square

Pere Callahan

Hi,

I recently became interested in some number theoretical questions. I have actually never really studied it before so my question might be really easy to answer.

I was trying to determine for which values of [itex]k[/itex] the number [itex]10^k+1[/itex] is divisible by a square. (Sloane A086982). The smallest such [itex]k[/itex] is 11 with the corresponding square being [itex]121=11^2[/itex]. Is it a coincidence that the number 11 occurs twice here? Is there anything more to say about this sequence?

Thanks for any hints or tips on how to start a problem like that.

Pere

Integral

Even after checking your link I do not understand the sequence. Does the ^ operator have some meaning other then exponentiation?

Pere Callahan

I will try to it differently. First, the ^ operator means exponentiation in this context.

We consider the sequence
[tex]
a_k=10^k+1
[/tex]
with first terms 1,11,101,1001 etc. We are now interested in the factorization of these numbers into primes and form the sequence of those [itex]k[/itex] such that in the factorization of [itex]a_k[/itex] at least one prime factors occurs at least twice.
Is this any clearer?
Thanks

Pere

sagardipak

Well, answering your question, the 11 plays a special role here. You can easily prove that [tex]10^k+1[/tex] is a multiple of 11 for every odd k.

Are you familiar with modular arithmetic? It is very helpful in number theory.

ramsey2879

Isn't it possible that any odd square not divisible by 5 has a multiplier such that the product would be 10^n + 1?

sagardipak

Are you saying that if n is an odd perfect square, then n divides a number of the form [tex]10^k+1[/tex]? If so, that is not correct. Take n=9. It will never divide any number of that form. Actually, the division will always have a remainder of 2. Check that ;)

ramsey2879

Conjecture, If [tex]10^n + 1[/tex] is divisible by a square then [tex]10^{n*(2b + 1)}+1[/tex] is also divisible by a square.

This is just my initial conjecture, after attempting to find a link between these values of A082986 and the corresponding square divisors of 10^n +1, I may be able to formulate a proof.

The members of A086982 which are not divisible by any other member thereof may be consider special, they are 11, 21, 39, 136, 171, 202, 243, 292, 406, 548

Hurkyl

That's becuase [itex]10^{n*(2b + 1)}+1[/itex] is divisible by [itex]10^n + 1[/itex].

ramsey2879

Actually, I did not specify my conjecture fully, See below

If [tex]n[/tex] is a member of A086982 then [tex]J = n*(2m)[/tex] is not a proper candidate for A086982; but [tex]J = n*(2m+1)[/tex] is since [tex](10^{n} + 1)|(10^{J} + 1)[/tex] in this case.

This holds for all values given so far for A086982. While the proof of the second part should have been clear to me, there is no clear proof or counterexample of the first part. Again the members of A086982 which are not divisible by any other member thereof may be consider special, they are 11, 21, 39, 136, 171, 202, 243, 292, 406, 548 and certain higher? values ( I'm not sure the list is accurate, i.e. should have been included or exhaustive up thru 548).

ramsey2879

I just noticed that 21,136, 171 and 406 are of the form n*(2n+1) and that 11, 39, 202,243,and 548 are either prime , a power of a prime or a non trivial factor of a number of the form n(2n+1) i.e. = n(2n+1)/k where k is a factor of n that is less than n. Also for n = 3 to 16 the only numbers n*(2n+1) for which either such a number or their non trivial factors are not members of A086982 are 4*9, 12*25 and 15*31 the first two have the unique form in that both n and 2n+1 are not square free, the third counter example has uniqueness in that both n and 2n+1 are of the form 2^k + 1. !7*35 looks like a strong candidate for A086982 since no factor thereof is listed as a member.

ramsey2879

I just found that [tex]10^{17*35} + 1[/tex] is square free if 54 497020 076810
017716 040927 608557 405847 236264 333227 546750 778971 918214 428885 291202
227775 405113 137115 258841 677550 279903 256040 392380 412335 715412 615161
800428 170614 659594 562308 948027 482104 464988 118707 445963 149192 232300
306040 545218 930623 450732 077479 288238 596378 359205 788267 673107 403311
663394 923771 384430 617482 147227 372985 571814 695405 129822 576204 213241
is square free; see below
10 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000001 = 11 x 103 x 4013 x 9091 x 14281 x 42841 x 87211 x 674731 x 909091 x 4
147571 x 787 223761 x 1868 879293 x 21993 833369 x 265212 793249 617641 x
5673 320472 670315 859129 x 40 410112 822629 936463 361201 x 160 220794
821014 452066 741918 303580 917664 386555 934641 x 103746 647830 421551
242486 430622 636901 002236 971549 990724 717454 338463 x 54 497020 076810
017716 040927 608557 405847 236264 333227 546750 778971 918214 428885 291202
227775 405113 137115 258841 677550 279903 256040 392380 412335 715412 615161
800428 170614 659594 562308 948027 482104 464988 118707 445963 149192 232300
306040 545218 930623 450732 077479 288238 596378 359205 788267 673107 403311
663394 923771 384430 617482 147227 372985 571814 695405 129822 576204 213241
(Composite)

The program has been runnung for 2 hours mostly to factor the latter composite factor.
I don't know how much longer it will take the program to arrive at all prime factors.

Hurkyl

Neither of these posts make sense to me; I can't decipher exactly what you're trying to say.

Incidentally, observe that for any m, if I set n = 2m, then m is a divisor of n(2n+1) satisfying |m| < |n|.

ramsey2879

It is like Fermat's little theorem where we know that p|m^{p-1} but sometimes p|m^{(p-1)/k}. In my conjecture if k is even then 10^(n*(2n+1)/k) + 1 is not square free while 10^(n(2n+1)) + 1 is, so there is a difference with my conjecture in that respect. The important values of A086982 are n(2n+1) and which factors of those are in the A086982 list and which are not, i.e.
1*3 = 3 no there is no odd prime divisor of n
2*5 = 10 no
3*21 yes
4*9 = 36 no
5*11 = 55 yes
6 * 13 = 78 39 is a member of A086982 but 78 is not
7 * 15 = 105 yes so is 21
8*17 = 136 yes
9 * 19 = 171 yes
10 * 21 = 210 no but 5* 21 is
11 * 23 = 253 yes
12 * 25 = 300 no
13 * 27 = 351 yes so is 39
14 * 29 = 1106 no but 553 is
15 * 31 ?? (I decided to look into this)
16 * 33 no but 33 is
17*35 ??
...
68*137 yes so is 68*137/17 = 548

There are of course many holes in my conjecture but the remarkable fact is that all of the basic members of A086982 (not divisible by another member) but 11 and 243 fit this conjecture.

CRGreathouse

1. You're trying to factor a 344-digit number. This could take longer than your lifetime.
2. It looks like you're using the alpertron ECM applet. ECM is good at finding small factors and bad at finding large factors.
3. You don't need to search for all factors; checking if the number is a square and searching up to the sixth root would suffice. Of course there's no good way to do that (since the sixth root is about 2e57); even ECMing to a good degree of confidence would be too time-consuming.

ramsey2879

Wow In that case I wonder how the sequence A086982 was created in the first place. Checking to see if it is a square would not do since it could be a square multiplied by still another factor. The only apparent method is to factor the number completely. Could it be possible to factor numbers of the form 10^m +1 where m ranges from 5 to 548 in say 10 years because that would seem to be the only way to create the listing of A086982 or are such factorizations already posted somewhere? I am going to take a look at the notes and reference for this sequence.

ramsey2879

[tex]10^{(17*7*5)} +1 = 11*(10^{4} -10^{3} + 10^{2} -10^{1}+1) *[/tex]
[tex](10^{6} - 10^{5} +10 ^{4} - 10^{3} + 10^{2} - 10 + 1) *[/tex]
[tex](10^{16} - 10^{15} \dots + 1) =[/tex]

11 * 9091 * 909091 * 9090909090909091 which can be factored further

CRGreathouse

If the number has no factors less than its third root, then it is squarefree unless it is a (prime) square. That's why I suggested testing the number to see if it's a square -- though it's not.