Blogging my thesis: what's Bernstein thinking?

In his paper called "How to find smooth parts of integers" Bernstein tries to find the 20-smooth part of the number x. He first finds the product of all the primes up to 20, which is 9699690.

Then he writes 9699690 mod x = r and claims that r can be represented as ab, where a = gcd(9699690, x) and gcd(b, x) = 1.

Why? Why would that be true? It's left without proof as if it was obvious, but it's not. What's Bernstein thinking? Why isn't the answer avaliable as a cute Disney DVD?



That's what I'm workin on in my thesis right now.

[Update] Argh, I messed it up. Bernstein doesn't, Pomerance does in his book where he discusses the method and apparently, he does it wrong.

Let's find the 5-smooth part of 22. We have 2*3*5= 30, 30 mod 22 = 8, gcd (30, 22) = 2, thus a = 2, b = 4 and gcd(22, 4) = 2, not 1. Gotcha!

That's what happens when you leave something as obvious instead of proving it properly.