# Tag Archives: primes

## Commutative Algebra 17

Field of Fractions Throughout this article, A denotes an integral domain (which may not be a UFD). Definition. The field of fractions of A is an embedding of A into a field K, such that every element of K can be … Continue reading

## Commutative Algebra 16

Gcd and Lcm We assume A is an integral domain throughout this article. If A is a UFD, we can define the gcd (greatest common divisor) and lcm (lowest common multiple) of two elements as follows. For , we can write the … Continue reading

## Commutative Algebra 15

Unique Factorization Through this article and the next few ones, we will explore unique factorization in rings. The inspiration, of course, comes from ℤ. Here is an application of unique factorization. Warning: not all steps may make sense to the … Continue reading

## 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

## 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

## 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

## 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

## 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