5

What is the sum of factors of factors of $33333333$ (that's $3$ eight times)?

Here's how I tried to attempt this question yet failed:

Factors of $33333333=3\times11111111=3\times11\times1010101=3\times11\times101\times10001$.

And now I was lost (just before the last step) as I couldn't confirm if 10001 is prime or not.

A solution I got: $10001=11025-1024=105^2-32^2=137\times73$ which are primes. But no way could I have myself figured out that 10001 is difference of those 2 squares.

Please help me in finding an easy way to check whether 10001 is prime or not and what it factors would as they lie too far to check manually, one-by-one, till $\sqrt{10001}=100$ (approx).

Edit: "just before the last step" above refers to the following step I would have done had I known the prime factorization:

Sum of all the factors of $33333333=(\frac{3^2-1}{3-1})\times(\frac{11^2-1}{11-1})\times(\frac{101^2-1}{101-1})\times(\frac{137^2-1}{137-1})\times(\frac{73^2-1}{73-1})=(3+1)(11+1)(101+1)(137+1)(73+1)$

InanimateBeing
  • 3,074
  • Why do you say that there is no way for you to write $10001=a^2-b^2$? A few tries, and you are done. – Dietrich Burde Jun 09 '22 at 14:53
  • 1
    $a^2+b^2$ is fine and that's not the problem, its $a^2-b^2$ that's hard to find own my own. – InanimateBeing Jun 09 '22 at 14:55
  • 1
    See also this post. And to find $10001=105^2-32^2$ is not hard, with a few tries. By the way, there are many more factors of $33333333$, for example $33333333=2409\cdot 13837$. So you have to sum up all possible factors, right? – Dietrich Burde Jun 09 '22 at 15:03
  • @DietrichBurde it insists upon Fermat theorem which is very useful apparently but are there other ways of finding the factors of 10001? Also, from the post you mentioned, "This is because the smallest positive integer k with" I wasn't able to understand anything after this, could you please explain it? – InanimateBeing Jun 09 '22 at 15:05
  • @DietrichBurde Please see the edit in my question – InanimateBeing Jun 09 '22 at 15:08
  • The difference of squares trick is due to Fermat. To go from $n^2 - k$ to $(n+1)^2 - k$ all you have to do is add $2n+1$. And ruling out that the result is a square is usually as easy as looking at the last couple digits. The difference of squares trick is effectively the same thing as trial division, but starting the checks near the square root. – DanielV Jun 09 '22 at 15:10
  • Sums of squares are easy to factor into Gaussian integers: $100^2 + 1^2 = (100 + i)(100 - i)$. This isn't much help for finding real factors, though. – Dan Jun 09 '22 at 15:48
  • @DanielV I have written this on the post about Fermat too but still I'm asking you too that I couldn't get why another prime dividing $10^8−1$ must be of the form $8k+1$. Please help me understand. – InanimateBeing Jun 09 '22 at 17:04

3 Answers3

4

Fermat's factoring technique is extremely fast for 10001.

$$101^2 - 10001 = 10201 - 10001 = 200$$ $$101\cdot 2 + 1 = 203$$ $$\begin{array} {r|c|l} 200 & 101 & \text{Obv not a square} \\ +203 \\ 403 & 102 & \text{Square can't end in 3} \\ +205 \\ 608 & 103 & \text{Square can't have digital root 5} \\ +207 \\ 815 & 104 & \text{Square can't have digital root 5} \\ + 209 \\ 1024 & 105 & \text{Found It} \\ \end{array}$$

Each odd row $(a,b)$ is $b^2 - n = a$, for example, $104^2 - 10001 = 815$. Eventually we find $105^2 - 10001 = 1024 = 32^2$, which implies $10001 = 105^2 - 32^2 = (105 + 32)(105 - 32) = 137 \times 73$.

Finding the $a$ is easy, just add. Ruling out that it is a square requires tricks. Like a square can only end in 1, 4, 5, 6, 9 (or 00) and only have a digital root of 1, 4, 7 or 9, which rules out 75% of them. You could make a large table that shows all possible 2 digit endings of squares which would rule out half of the remaining possibilities. And sometimes, at worst, you'd just have to check if a number is a square by squaring an estimate of it's square root.

DanielV
  • 23,556
2

Honestly, there isn't a very good way to factor 10001 without just brute forcing through every prime up to 100. As you said, the difference of squares is very hard to find, and that method shouldn't be used unless it is extremely obvious (for example, the number 9991). Once you find the primes, you can easily find the sum of all the factors using the method you described in your edit.

Fatso Boo
  • 692
2

There's no known fast general algorithm for factoring integers. (Indeed, the RSA cryptosystem relies on the assumption that factoring is hard.)

One thing that might help somewhat is to write your numbers in base six, which makes it easier to identify primes because there are only two digits that a prime number (other than 2 or 3) can end with: 1 or 5.

$10001_{10} = 114145_6$. This ends in a 5, so it might be a prime number. To narrow down possible factors, consult the multiplication table:

1 2 3 4 5
2 4 0 2 4
3 0 3 0 3
4 2 0 4 2
5 4 3 2 1

In order to get a 5 as the last base-6 digit, one factor must end in 1, and the other must end in 5.

The 25 prime numbers less than $\sqrt{10001}$ break down as follows:

  • 11 whose last base-6 digit is 1: 11 (7), 21 (13), 31 (19), 51 (31), 101 (37), 111 (43), 141 (61), 151 (67), 201 (73), 211 (79), 241 (97)
  • 12 whose last base-6 digit is 5: 5, 15 (11), 25 (17), 35 (23), 45 (29), 105 (41), 115 (47), 125 (53), 135 (59), 155 (71), 215 (83), 225 (89)
  • 2 special cases that are obviously not factors here: 2, 3

So, instead of trying all 25 primes, you just need to try the 11 "1" primes, if there's a factor, division will get you the corresponding "5" prime.

$$114145_6 = 201_6 \times 345_6$$ $$10001 = 73 \times 137$$

Dan
  • 14,978
  • 1
    Woow! This sure goes a long way! Thanks, that's why I love this site! Upvoted. – InanimateBeing Jun 09 '22 at 16:28
  • 1
    Interesting, but I do not see why you would only need to test the primes $\le \sqrt{10001}$ which are $1$ mod $6$. For one thing, it could be the productof three primes that are $5$ mod $6$, but even if it were a semiprime, then you would be looking for the least prime that divides $10001$: while you could say that one of them is $1$ mod $6$, you cannot be sure that it's the smallest one. See for instance $899=29\times 31$. If anything, you can be sure that one prime equal to $5$ mod $6$ divides the number, but again you can't be sure it's the smallest one. – Sassatelli Giulio Jun 09 '22 at 16:44
  • 1
    Nice observation, being a product of three primes that are 5 mod 6 is problematic indeed. – InanimateBeing Jun 09 '22 at 16:58
  • @InanimateBeing It's not as much of a problem as the other one is: say I've already told you that no prime $\le\sqrt[3]{10001}$ divides $10001$ (i.e., that the number is the product of at most two primes). Still, you cannot make the simplification that Dan is claiming, because you do not know if it's a number like $73\times 137$ (where the prime $\le\sqrt n$ is $1$ mod $6$) or like $29\times 31$ (where the prime $\le\sqrt n$ is $5$ mod $6$). And if you look at this with knowledge of the fact that $(\Bbb Z/m\Bbb Z)^*$ is a group, it gets worse. – Sassatelli Giulio Jun 09 '22 at 17:18
  • @SassatelliGiulio: Good point. My "shortcut" only works if it's known in advance that the number has at most two prime factors. So you'd first need to check all primes up to $\sqrt[3]{10001}$ (i.e., 2, 3, 5, 7, 11, 13, 17, and 19) before applying it. – Dan Jun 09 '22 at 21:17
  • @Dan You are still wrong, and I won't explain a third time why. – Sassatelli Giulio Jun 09 '22 at 21:40