Help in understanding Bouman's method for factoring

Mental Calculation, Mathematics, and Puzzles
1

Here: https://www.recordholders.org/downloads/worldcup/factorization-tutorial.pdf is to be found the method that the great Dutch mental calcualtor Willem Bouman uses for factoring.

From what I (think) I’ve understood from Bouman’s tutorial, he uses this approach:

To begin, he calculates the square root of the number we want to factor (let’s call it “n”). Once he’s calculated the square root of “n”, he tests the divisors less than the result of the square root (let’s call them “r”).

Then, he checks if “n” (mod “p” = 0), where “p” is the prime number in the list of divisors less than the result of the square root.

He uses the question “Is the number to be factored even or odd?” as a filter.

If it’s even, you only need to divide by 2; if the number is odd, he discards all the even divisors and focuses on the odd divisors like 3, 5, 7, 9, etc.

However, this is where my understanding ends, because when Mr. Bouman uses the number 6.953 as an example on page 4, he states that it should leave a remainder of 5 after being divided by the modulo 9:

6.953 = 5(9), which is 6.953 = 5 (mod 9). After this, he uses tables, and this is where my confusion lies.

If anyone can help me, I would be very grateful. I know it’s a difficult topic. Thank you very much.

1 Like
2

(Excuse any over-explaining; it’s better to tell you something you know already again rather than leaving something out)

When we divide a number and we do not divide up units then we might have a remainder. The remainder is interesting in its own right, so we call the operation of finding the remainder after dividing by a number modulo or mod.

So 6 953 mod 9 is 5.

(Sorry I can’t bear to write 6.953 - where I come from . is a decimal point and we use , as thousands separator)

6 953 = 772*9+5

There is a useful trick for finding mod 9 for decimal number called casting out nines.

You add all the digits making up a number. Leave out nines and mod 9 as you go.

For 6 953:

6 + 5

(Skipped the 9)

11 so far

It’s bigger than 9 so add them first

1+1

2

Now add 3

5

So 6 953 mod 9 is 5.

We don’t even need to go find the 772 by division.

1 Like
3

This is (I guess), what all calculators do. Let’s assume a number N has at least 2 factors.
If not, it would be prime.
We write: N = p\times q.

If p is lower than the \sqrt{N}, than q needs to be higher than the \sqrt{N} (or the other way round).
One of the factors needs to be lower than the \sqrt{N}.
If we cannot find a factor and we have checked all primes under \sqrt{N}, then the number N is prime.

Simple example. N=65, 65 = 5\times 13 and \sqrt{N}\approx 8.
One factor is lower than 8, the other is higher than 8.

1 Like
4

I am going to be honest.
In his text, there is a lot to unpack.

This text is dense. He explains a lot in his Magnum Opus.
He uses modulo calculation, he has mental builds in his head about even hundreds and odd hundreds and how this effects the total if you add them.

See Amazon.com: Willem Bouman: books, biography, latest update for his book.

I have read his book. Deeply. I was even one of the editors. However; after 10 years, I really have to become reacquainted with his style of calculating.

And, since he is a dear friend of mine, I will ask him personally how he, for example treats a number like 6,953.

So, give me some time to work on this and hopefully I can make this a lot clearer.

1 Like
5

Thank you!! I really appreciate this!!

6

I know the system now.
Let’s do some examples.
Here is the first.

Let’s take 6953 = 83^2 + 8^2 = 77^2 + 32^2.

Using Wims method, we start with:
a = 83, b=8, c=77, d=32.

p = (a+c)/2 = (83+77)/2 = 80
q = (a-c)/2 = (83-77)/2 = 3
r = (b+d)/2 = (32+8)/2 = 20
s = (b-d)/2 = (32-8)/2 = 12

Now we make 2 pairs:
Pair A: (p, r) with (q, s)
Pair B: (p, s) with (q, r)

For each pair, find the greatest common denominator.
Pair A:
(p, r) = (80, 20), gcd = 20,
(q, s) = (3, 12), gcd = 3

20^2+3^2 = 400+9 = 409.

Factor one is 409.

Pair B:
(p, s) = (80, 12), gcd = 4,
(q, r) = (3, 20), gcd = 1
4^2+1^2 = 16 + 1 = 17.

Factor two is 17.

6953 = 17\times 409

1 Like
7

But I don’t really understand where these numbers come from.

Why is a 83, b is 8, etc.?

8

We want to write the number 6 953 as the sum of two squares.
And we want to find two versions of the sum of two squares.

Mathematically, we want to see: N = a^2 +b^2 = c^2+d^2, and in this case N = 6953.

The square root of 6953 is a little more than 83 and a little less than 84.
Let’s start with 83.

83^2 = 6889
6953 - 6889 = 64 = 8^2

Therefore: 6953 = 83^2 + 8^2.
We have the first sum!

Remember. We are looking for N = a^2 +b^2 = c^2+d^2.

We found a and b.
The next step is to find c and d.

Finding the second one

We’ll step down from 83 to 82, 81, 80, and so on, while checking each time if the remainder becomes a perfect square.

We’re looking for numbers (x,y) such that 6953 = x^2 + y^2, with y also a square.

The difference between consecutive squares is easy to compute: 83^2 - 82^2 = 83 + 82 = 165.

That means every time we reduce x by 1, we add x + (x+1) or 2x+1 to the remainder.

Step-by-step process

I’ll show the calculation twice.
This shows the process:
\begin{aligned} 6953 &= 83^2 + 8^2 \\ &= 82^2 + 165 + 8^2 \\ &= 81^2 + 163 + 165 + 8^2 \\ &= 80^2 + 161 + 163 + 165 + 8^2 \\ &= 79^2 + 159 + 161 + 163 + 165 + 8^2 \\ &= 78^2 + 157 + 159 + 161 + 163 + 165 + 8^2 \\ &= 77^2 + 155 + 157 + 159 + 161 + 163 + 165 + 8^2 \\ \end{aligned}

In numbers, it looks like this:
\begin{aligned} 6953 &= 83^2 + 8^2 \\ &= 82^2 + 229 \\[3pt] &= 81^2 + 328 \\[3pt] &= 80^2 + 489 \\[3pt] &= 79^2 + 648 \\[3pt] &= 78^2 + 808 \\[3pt] &= 77^2 + 1024. \end{aligned}

Bingo!
1024 = 32^2\rightarrow 6953 = 77^2 + 32^2.

Summary

By stepping down from the first square 83^2 and accumulating the consecutive differences of squares, we eventually reach a remainder that itself is a perfect square 32^2.

We found two ways of showing 6953 as the sum of two squares:
\boxed{6953 = 83^2 + 8^2 = 77^2 + 32^2 = (4^2+1^2)(20^2+3^2) = 17\times409.}

p.s.: tomorrow I’ll take an easier number, like 65 or so.

2 Likes
9

Let’s do a much simpler example and factorize 65.

65 = 8^2 + 1^2 = 7^2 + 4^2.

Using Wim’s method, we start with a = 8, b = 1, c = 4, d = 7.

p = (a + c)/2 = (8 + 4)/2 = 6
q = (a - c)/2 = (8 - 4)/2 = 2
r = (b + d)/2 = (1 + 7)/2 = 4
s = (b - d)/2 = (7 - 1)/2 = 3

Now we make two pairs:

  • Pair A: (p, r) with (q, s)
  • Pair B: (p, s) with (q, r)

For each pair, find the greatest common divisor (gcd).

Pair A:
(p, r) = (6, 4), gcd = 2
(q, s) = (2, 3), gcd = 1
2^2 + 1^2 = 4 + 1 = 5

Factor one is 5.

Pair B:
(p, s) = (6, 3), gcd = 3
(q, r) = (2, 4), gcd = 2
3^2 + 2^2 = 9 + 4 = 13

Factor two is 13.

\boxed{65 = 13 \times 5.}

1 Like
10

Isn’t there a shorter way to calculate all those sums?

11

But then what is the purpose of all those tables that Mr. Bouman proposes in his booklet?

12

Of course there is!
=77^2+155+157+159+161+163+165+8^2\implies
=77^2+(155+157+159+161+163+165)+8^2\implies
=77^2+3\times(155+165)+8^2\implies
=77^2+3\times(320)+8^2\implies
=77^2+960+8^2\implies
=77^2+1024\implies
=77^2+32^2\implies

1 Like
13

In my previous post, I started with 65 = 8^2 + 1^2 = 7^2 + 4^2.

This is all nice and easy when given, but if you don’t know which sums of squares are contained within 65, then you will have to find them.

We will do that now.

How to get sum of squares out of 65.

So one option - and we will get to some cleverer options later - is to start with the highest possible square and step down from this number until we find them.

Btw, if we find one or zero sums of squares, then the number is prime!

Although time consuming; it is the most straightforward way!

We have done this earlier in this thread. Only now, the numbers are easier to contain and calculate.

As per mr. Boumans instructions, start with \sqrt{65}\approx 8.

This means the highest possible number for one of the squares is 8 and 8^2 = 64.

65 - 8^2 = 65 - 64 = 1 = 1^2.

This gives us immediately the first sum:

65 = 8^2 + 1^2.

After 8, let’s try 7.

7^2 = 49 and 65-49=16=4^2.

Here we find the second sum:

65 = 7^2 + 4^2.

6^2 = 36. 65 -36 = 29. \hspace{2cm}29 is not a square.
5^2 = 25. 65 -25 = 40. \hspace{2cm}40 is not a square.
4^2 = 16. 65 -16 = 49. \hspace{2cm}49 is a square, but we already found this combination.
3^2 = 9. 65 -9 = 56. \hspace{2.5cm}56 is not a square.
2^2 = 4. 65 -4 = 61. \hspace{2.5cm}61 is not a square.
1^2 = 1. 65 -1 = 64. \hspace{2.5cm}64 is a square, but we already found this combination.

Done. After 7, there are no more squares.

I’ll post about some cleverer strategies later.

1 Like
14

Imagine I go here: Prime Factorization and it shows me: factor 28,304

Its square root is approximately 168.

168 × 168 = 28,224

28,304 - 28,224 = 80

80 is approximately 64, the square of 8.

80 - 64 = 16, which is the square of 4.

So 28,304 = 168² + 8² + 4²

= 28,224 + 64 + 16 = 28,304

But the Number Factorizer shows that 28,304 is 2^4 × 29 × 61 Number factorizer - integer factorization up to 70 digits

I don’t know what I’ve done then if it’s not factoring.

15

Just a few cents of my knowledge, I don’t know what’s going on here.
But above you are giving examples of 28224 + 64 + 16 = 28304 (as sum)

and below is basically products, 2^4 x 29 x 61 = 28304 (as products)
If I were to convert this in the same way you did, it would look like this to me.
2^4 = 16
16 x 29 = 464
464 x 61 = 28304
16 + 464 + 28304 (to me, this is what you did, but since childhood, I have mostly worked with factors as products, maybe I didn’t understand what you wanted to achieve, so it might not be helpful.)

16

Dear Ben!

I’ll explain what went wrong. However; my father just died and I may need some time.

Also; I explained the method now in an easy to understand method.
The magic, how Willem quickly knows which number to take and which ones to avoid, I have to explain later.

17

I’m truly sorry for your loss. I lost my father 7, 8 months ago, so I understand how heavy this moment can feel. Please take all the time you need – the explanation can wait.
Wishing you strength.

18

Dear Harald!!

Please accept my deepest condolences to you and your family!!!

Take all the time you need!!