Tag Archives: intermediate

Quadratic Residues – Part III

Posted on November 18, 2011 by limsup

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 | Tagged , , , , | Leave a comment

Quadratic Residues – Part II

Posted on November 16, 2011 by limsup

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 | Tagged , , , | Leave a comment

Quadratic Residues – Part I

Posted on November 15, 2011 by limsup

[ 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 | Tagged , , , | Leave a comment

Order of an Element Modulo m and Applications – Part II

Posted on November 6, 2011 by limsup

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

Order of an Element Modulo m and Applications – Part I

Posted on November 6, 2011 by limsup

Background required : modular arithmetic If you’ve any experience observing powers of numbers, you’d have noticed that the last digit runs in cycles: e.g. if you take the last digits of successive powers of 7, you get 7 → 9 → … Continue reading →

Posted in Notes | Tagged , , | Leave a comment