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

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

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 | Tagged , , , , , | 2 Comments