# Tag Archives: number theory

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

## Casual Introduction to Group Theory (3)

Subgroups [ This article approximately corresponds to chapter III of the group theory blog. ] Let G be a group under operation *. If H is a subset of G, we wish to turn H into a group by inheriting the operation from G. Clearly, … Continue reading

## Modular Arithmetic Deluxe Edition

[ Background required: standard modular arithmetic. ] Consider the following two problems: Problem 1. Prove that if p > 2 is prime, then when is expressed in lowest terms , m must be a multiple of p. Problem 2. Prove that if … Continue reading

## Thoughts on a Problem II

The following problem caught my eye: (USAMO 1997 Q3) Prove that for any integer n, there is a unique polynomial Q(X) whose coefficients all lie in the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and Q(-2) … Continue reading

## Sample Problem Solving + Homework Hints

In this post, I’ll talk about basic number theory again. But I’ll still assume you already know modular arithmetic. 🙂  In the first part, there’ll be some sample solutions for number theoretic problems, some of which were already presented in … Continue reading

Posted in Notes | | 2 Comments

## Quadratic Residues – Part IV (Applications)

Let p be an odd prime and g be a primitive root modulo p. Given any a which is not a multiple of p, we can write for some r. We mentioned at the end of the last section that a is a square if … Continue reading

Posted in Notes | | 3 Comments

## Quadratic Residues – Part III

Ok, here’s the third installation. Getting a little tired of repeatedly saying “a is/isn’t a square mod p“, we introduce a new notation. Definition. Let p be an odd prime and a be an integer coprime to p. The Legendre symbol … Continue reading