Tag Archives: primes

Primality Tests III

Solovay-Strassen Test This is an enhancement of the Euler test. Be forewarned that it is in fact weaker than the Rabin-Miller test so it may not be of much practical interest. Nevertheless, it’s included here for completeness. Recall that to … Continue reading

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

Primality Tests II

In this article, we discuss some ways of improving the basic Fermat test. Recall that for Fermat test, to test if n is prime, one picks a base a < n and checks if We also saw that this method would utterly fail … Continue reading

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Primality Tests I

Description of Problem The main problem we wish to discuss is as follows. Question. Given n, how do we determine if  it is prime? Prime numbers have opened up huge avenues in theoretical research – the renowned Riemann Hypothesis, for … Continue reading

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Topics in Commutative Rings: Unique Factorisation (3)

Example 1: The Gaussian Integers Z[i] Let’s pick the norm function N : Z[i]-{0} → N where N(a+bi) = (a+bi)(a–bi) = a2+b2. We know that N is a multiplicative function, i.e. N(r)N(s) = N(rs). Instead of checking this by brute force, we write N(x) = x·xc, where (a+bi)c = a-bi is the conjugate of a+bi. It’s easy to … Continue reading

Posted in Notes | Tagged , , , , , , , , , , , | Leave a comment

Topics in Commutative Rings: Unique Factorisation (2)

In the previous article, we imposed certain finiteness conditions on the ring (specifically a.c.c. on principal ideals: that every increasing sequence of principal ideals is eventually constant), then proved that unique factorisation holds if and only if all irreducible elements … Continue reading

Posted in Notes | Tagged , , , , , , , , , | Leave a comment

Topics in Commutative Rings: Unique Factorisation (1)

Unique Factorisation: Basics Throughout this post, let R be an integral domain; recall that this means R is a commutative ring such that whenever ab=0, either a=0 or b=0. The simplest example of an integral domain is Z, the ring of integers. What’s of interest to … Continue reading

Posted in Notes | Tagged , , , , , , , | Leave a comment