Instructive Examples in Kraitchik’s Method

While discussing the history of the modern factoring, Carl Pomerance’s 1996 expository piece “A Tale of Two Sieves” describes a factoring algorithm called Kraitchik’s Method and demonstrates the algorithm by factoring 2041.

The example is nice; certainly nicer and more illustrative than what you might produce at random. But exactly how special is Pomerance’s 2041 example?

Read Article →

Dirichlet’s Theorem and Sieves

Dirichlet’s Theorem on the infinitude of primes in arithmetic progressions relies on the non-vanishing of non-trivial Dirichlet characters at 1.

In this post, I’ll show how this reduction can be introduced in an intuitive way via sieve theory. If we actually sieve, we obtain estimates for the number of integers whose prime factors lie in given congruence classes.

Read Article →