Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisible by a square

  1. Jul 21, 2008 #1
    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
     
    Last edited: Jul 21, 2008
  2. jcsd
  3. Jul 22, 2008 #2

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Even after checking your link I do not understand the sequence. Does the ^ operator have some meaning other then exponentiation?
     
  4. Jul 22, 2008 #3
    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
     
  5. Jul 22, 2008 #4
    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.
     
  6. Jul 23, 2008 #5
    Isn't it possible that any odd square not divisible by 5 has a multiplier such that the product would be 10^n + 1?
     
  7. Jul 23, 2008 #6
    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 ;)
     
  8. Jul 26, 2008 #7

    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
     
    Last edited: Jul 26, 2008
  9. Jul 26, 2008 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's becuase [itex]10^{n*(2b + 1)}+1[/itex] is divisible by [itex]10^n + 1[/itex].
     
  10. Jul 27, 2008 #9
    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).
     
  11. Jul 27, 2008 #10
    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.
     
  12. Jul 27, 2008 #11
    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.
     
  13. Jul 27, 2008 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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|.
     
  14. Jul 28, 2008 #13
    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.
     
    Last edited: Jul 28, 2008
  15. Jul 28, 2008 #14

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  16. Jul 28, 2008 #15
    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.
     
  17. Jul 29, 2008 #16
    [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
     
    Last edited: Jul 29, 2008
  18. Jul 29, 2008 #17

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  19. Jul 29, 2008 #18

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Looking into it a little, I see that nothing more is known than what I posted:


    Algorithms in algebraic number theory
    The factorization of the ninth Fermat number

    Of course anyone knowing otherwise is encouraged to post.
     
  20. Jul 30, 2008 #19
    Yes I am using the ECM applet. I have a couple of question I assumed that every factor listed has been checked as a divisor of the last composite factor, but maybe I am not correct. If, supposing that the program factored 10^565 + 1 algebraically then individually factored each of these components, would it check all factors of the factored components as a factor of the other components before continuing on with the factoring routine? If not then maybe I should enter the larger known factors for testing as a factor of the unfactored expression. Two apparently there are numbers known as Cunningham numbers which tend to be factors of the form A^n + 1. I see that the applet has automatically check the box to try these factors as I entered 10^595 + 1 as the expression to factor. How many of the factors listed by the applet in my case as prime factors are known as Cunningham factors? Obviously there is no need to worry that those haven't been checked as a factor of the unfactored component.
     
  21. Jul 30, 2008 #20
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Divisible by a square
  1. Divisibility question (Replies: 12)

  2. Divisibility Question (Replies: 6)

  3. Division ring (Replies: 0)

Loading...