Math Forum / Mathematics / Undergraduate Math / January 2009

Can you come up with _any_ algorithm to find a factor of x or deduce
that it's prime? There's an obvious one - how many divisions does it
take?

There are various versions of the "obvious" one - it may happen that
your obvious version takes only sqrt(x) divisions and you're set.
Or you may come up with the obvious version that takes x divisions;
in that case think about how you might improve it to sqrt(n).

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)

Well, one thing that comes to mind is to note that log_2(x) is the
number of digits of x when x is represented in base 2.

Suppose x > y (if not, swap x and y).  If x has more binary digits than
y, then x % y will have less digits than x, since x % y < y.  If x and
y have the same number of binary digits, then again x % y will have
less digits than x, because x < 2y, and so x % y = x - y, and when you
subtract two numbers with the same number of digits in binary, you get
a number with less digits.

You can probably take it from there.

Or, you can apply the general algorithm that is used for most problems
of this nature: look in Knuth. :-)

Thank you very much David, Tim and Virgil.  I worked on this problem working
with the hints of Tim and David in particular and proved the result.  In
fact, the nicest proof seems to be by usin induction on n=x+y.  The sqrt(x)
bound that David mentions was also easy to obtain by just thinking of how
one checks if a no. is prime--I should have got that, sorry!

Thanks again. You've been a great help.