# Tag Archives: number theory

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

Posted in Notes | | Leave a comment

## Quadratic Residues – Part II

Recall what we’re trying to do here: to show that if p > 2 is prime and a is not a square modulo p, then . As mentioned at the end of the previous part, we will need… Primitive Roots Again, let … Continue reading

Posted in Notes | | Leave a comment

## Quadratic Residues – Part I

[ Background required : modular arithmetic. Seriously. ] Warning: many of the proofs for theorems will be omitted in this set of notes, due to the length of the proofs. The basic question we’re trying to answer in this series … Continue reading

Posted in Notes | | Leave a comment

## Number Theory Homework (2 Weeks)

Homework problems for 5 Nov 2011: Let a1, a2, … be a series recursively defined as follows: a1 = 20, a2 = 11, and for n ≥ 1, an+2 is the remainder when an+1 + an is divided by 100. … Continue reading

Posted in Homework | Tagged , , | 2 Comments

## Thoughts on a Problem

From time to time, I may post my experience in solving a specific problem including some wrong twists and turns I’ve taken, as well as the motivation for some rather cryptic constructions. Warning : since this post documents my thought … Continue reading

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

## Order of an Element Modulo m and Applications – Part II

Having introduced the concept of the (multiplicative) order of a modulo m, let us use it to solve some problems. Problem 1. Prove that if n > 1 is an integer, then n does not divide 2n – 1. Proof. … Continue reading

Posted in Notes | Tagged , , | 2 Comments