Category Archives: Number Theory

Generating a random variable by coin tossing


1. Coin tossing Suppose we are given a sequence of independent fair bits (meaning take and with probabily ) we want to produce with them a discrete random variable that takes the values with probabilities . The objective, of course, … Continue reading

Posted in Algorithms, Number Theory, Probability | Leave a comment

Partitions and divisors


The number of partitions of a non-negative integer is, roughly speaking, the number of ways in which we can write as a sum of positive integers disregarding the order of the terms, and we denote this number by . Formally … Continue reading

Posted in Combinatorics, Number Theory | Tagged , | Leave a comment

Finite fields and trinomials


In this post we shall prove that is irreducible in , thus proving there are infinitely many irreducible trinomials over . Maybe my proof is overcomplicated, so if you have a simpler one, go ahead and comment. First remember that … Continue reading

Posted in Algebra, Number Theory | Tagged | Leave a comment

Cyclotomic Polynomials


Okay, here is a proof of a particular case of Dirichlet’s Theorem on Arithmetic progressions. As a preliminary, we will begin by looking at the cyclotomic polynomials. Definition 1 Given we define , the -th cyclotomic polynomial, to be the … Continue reading

Posted in Algebra, Number Theory | Leave a comment

Eisenstein’s criterion


In this post we will see a couple of criteria to prove that a given polynomial in is irreducible over . As a reminder, a polynomial over is irreducible over if and only if it cannot be written as the … Continue reading

Posted in Algebra, Number Theory | Leave a comment

Number of divisors


It has been a long time since the last number theory post, so, in this post we are going to approximate the value of where denotes the number of divisors of by a somewhat funny method (since there are some … Continue reading

Posted in Number Theory | Leave a comment

Irreducible polynomials over Z_P


Okay, today we are going to talk about the number of irreducible polynomials of a given degree over . One of the main results will be the following Proposition 1 Let be a prime number and let be the product … Continue reading

Posted in Algebra, Generating Functions, Number Theory | 1 Comment