-
Recent Posts
Archives
- March 2023
- January 2023
- May 2020
- April 2020
- March 2020
- June 2018
- July 2016
- June 2016
- May 2016
- March 2015
- February 2015
- January 2015
- December 2014
- December 2013
- November 2013
- July 2013
- June 2013
- May 2013
- March 2013
- February 2013
- January 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
Categories
Meta
Pages
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
Posted in Uncategorized
Tagged cryptography, elementary, jacobi symbol, legendre symbol, number theory, primality tests, primes, programming
Leave a comment
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
Posted in Uncategorized
Tagged carmichael numbers, cryptography, elementary, number theory, primality tests, primes, pseudoprimes
Leave a comment
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
Posted in Uncategorized
Tagged carmichael numbers, cryptography, elementary, number theory, primality tests, primes, pseudoprimes
Leave a comment
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
Posted in Notes
Tagged cyclic groups, generated groups, group theory applications, groups, intermediate, number theory, subgroups
Leave a comment
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
Posted in Notes
Tagged basic, congruence, modular arithmetic, notes, number theory, rational numbers
Leave a comment
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
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
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
Tagged intermediate, legendre symbol, notes, number theory, quadratic residues
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
Mathematics and Such 