Math 105 (Fall 2025)

November 26:

November 24:

November 21:

November 19: 

November 17: Midterm 2 review

November 14: We showed that for p an odd prime (a/p) ≡ a^{(p-1)/2} (mod p) using our computation of order of g^k where g is a primitive root modulo p. We then derived all Pythagorean triples that are primitive, i.e., (a, b, c) satisfying a^2 + b^2 = c^2 with a, b, and c having no common divisors.

November 12: We discussed how to use congruences to show that a given Diophantine equation needn't have any solutions over the integers. The idea is to ``reduce mod p" where p is a prime --- this just means considering the same equation mod p --- and then show that there are no solutions mod p. I then defined the notion of a Quadratic residue and introduced the Legendre symbol.

November 10: After proving some preliminary results, we computed the order of a^k mod n to be r/gcd(r, k), where r = ord_n(a). We showed that x^2 + 1 ≡ 0 (mod p) has a solution if and only if p = 2 or p ≡ 1 (mod 4). We finally introduced Diophantine equations, talked about Hilbert's tenth problem. and discussed how to use factoring to obtain solutions.

November 07: We proved the existence of primitive roots modulo a prime p. In fact, we proved the stronger result: given d | (p-1), there exists phi(d) distinct primitive d-th roots mod p. We then saw that given a primitive root a mod p, the elements a, a^2, a^3, ..., a^{p-1} form a reduced residue system mod p. 

November 05: We proved Wilson's theorem: for a prime p, we have (p-1)! ≡ -1 (mod p). The point is that by Euler's theorem, the integers 1, 2, ..., p-1 are solutions to the equation x^{p-1} - 1 ≡ 0 (mod p) therefore we obtain a factorization x^{p-1} - 1 ≡ (x-1)(x-2) ... (x - (p-1)) (polymod p), and we obtain Wilson's theorem by substituting x = 0 in that equation. Given coprime integers a and n, the order of a mod n, denoted ord_n(a), is the smallest positive integer r such that a^r ≡ 1 (mod n). By Euler's theorem, we have ord_n(a) <= phi(n). In class, we proved that ord_n(a) divides phi(n) and moreover that if a^m ≡ 1 (mod n), then ord_n(a) divides m.

November 03: If we are working modulo a prime, we are able to iterate the factorization result from last class: if a1, a2, ..., ar are distinct roots of f(x) ≡ 0 (mod p), then there exists g(x) in Z[x] such that f(x) ≡ (x-a1)(x-a2)...(x-ar) g(x) (polymod p). This result can fail over non prime integers: mod 8, 1 and 3 are roots of x^2 - 1 but we cannot write x^2 - 1 as (x-1)(x-3)g(x) (polymod 8). We then defined the degree mod n of a polynomial f(x) and saw that the number of distinct solutions of f(x) ≡ 0 (mod n) is at most the degree mod n of f(x).

October 31: We saw the following formula for the Euler totient function (n) = n*(1-1/p_1)*(1 - 1/p_2)...(1 - 1/p_r) where p_i are the distinct prime factors of n (counted without multiplicity). We then defined the set of integer polynomials in the variable x, denoted Z[x] and defined an equivalence relation "polymod n", where n is an integer > 1 by the formula f ≡ g (polymod n) if for all r, we have a_r ≡ b_r (mod n) where a_r and b_r are the coefficients of x^r in f and g respectively. We proved two lemmas: f ≡ g (polymod n) if and only if there exists a polynomial h in Z[x] such that f(x) - g(x) = nh(x), and given a in Z such that f(a) ≡ 0 (mod n), there exists h(x) in Z[x] such that f(x) ≡ (x-a) h(x) (polymod n).

October 29: We proved Euler's theorem: given an integer a coprime to n, then a^{phi(n)} ≡ 1 (mod n); and Fermat's Little theorem: given a prime p and any integer a, we have a^p ≡ a (mod p). Both of these results follow from a simple proposition,: Let {a1,a2,...,an} be a complete residue system modulo n, and {a1, a2, a3,..., a_(n)} be a reduced residue system modulo n, and a and b be integers with (a, n) = 1. Then the set {a a1 + b ,a a2 + b,...,a an + b} is also a complete residue system modulo n, and similarly {a a1, a a2, a a3,..., a a_(n)}is a reduced residue system modulo n. We finally proved that the Euler totient function is multiplicative.

October 27: We defined the notions of a Complete Residue System mod n and a Reduced Residue System mod n. We saw that a reduced residue system mod n can be obtained by starting with a complete residue system, and then removing all elements that are not coprime to n. We also saw that every RRS mod n has the same cardinality, which we define to be φ(n). the Euler totient function. Midterm 1 has been graded -- please come to OH if you have regrade requests.

October 24: We proved the Chinese Remainder Theorem: given two coprime integers m and n, we can simultaneously solve x ≡ a mod m and x ≡ b mod n and this solution is unique mod mn. We did an example in class, and proved the following generalization via induction: given r > 1 equations of the form x ≡ a_i mod n_i where the n_i’s are relatively coprime (i.e., n_i and n_j are coprime if i and j are different), there is a unique solution for x mod (n_1 n_2 … n_r).

October 20: Midterm practice in class; midterm from 7pm to 8pm in Warren Lecture Hall 2111.

October 17: We talked about solving linear equations with one variable mod n -- three examples revealed to us that this is subtle. The upshot of today's lecture was the following algorithm to solve ax ≡ b (mod n). Case (1): gcd(a, n) = 1. In this case, write 1 = ra + sn by Bezout's idenitity. Multiplying the original equation by r, we get that ra x ≡ rb (mod n). But ra ≡ 1 (mod n) since ra + sn = 1, so we get that x ≡ rb (mod n). Case (2): gcd(a, n) = d > 1. If d does not divide b, then there are no solutions; if insted d divides b, then the solutions of the original equation are the same as the solutions of the equation (a/d) x ≡ (b/d) (mod (n/d)) and this puts you back into Case (1). Please try the two problems I gave at the end of the lecture to see if you understand what we covered in this lecture (solve 7x  ≡ 13 (mod 17) and solve 4y  ≡ 12 (mod 16).

October 15: We proved the theorem from last time, and then defined Congruences: we say a is congruent to b mod n, if n divides (a - b). So mod 10, 1 is congruent to both 11 and -9. We showed that a is congruent to a mod n (reflexivity), if a is congruent to b mod n, then b is congruent to a mod n (symmetry), and if a is congruent to b mod n and b is congruent to c mod n, then a is congruent to c mod n (transitivity). What is most important is that this relationship works well with addition and multiplication: if a is congruent to b mod n and c is cognruent to d mod n, then a+c is congruent to b+d mod n, and ac is congruent to bd mod n. 

October 13: We proved that if f is multiplicative, then S_f is also multiplicative. This allows us to provide explicit formulas for sigma and d, where sigma is the sum of all divisors function and d is the number of divisors function, in terms of the prime factorization of n. We then stated the theorem about solutions to a linear diophantine equation Ax + By = C: this has no solution if d:= gcd(A, B) does not divide C, and if d divides C then it has infinitely many solutions which can be parametrized by (x_0 + tB/d, y_0 - t A/d) where (x_0, y_0) is a particular solution.

October 10: We did a worksheet in class (find on Canvas). Please complete this before Monday's lecture. We saw that a multiplicative function is fully determined by its value on prime powers.
For a function f: N ---> C, we defined the function S_f by the formula S_f(n) = sum of f(d) as d varies over all divisors of n [so S_f(10) = f(1) + f(2) + f(5) + f(10)]. We stated the theorem that if f is multiplicative, then S_f is also multiplicative.

October 08: Proved the following result: for coprime integers m and n, every divisor d of mn factor uniquely as d = d1 d2 with the property that d1 is a divisor of m and d2 is a divisor of n. Conversely, given integers d1 and d2 such that d1 divides m and d2 divides n, we have d = d1 d2 divides mn (converse is obvious). Therefore, for coprime integers m and n, there is a bijection
{divisors of mn} <----> {divisors of m} x {divisors of n}.
We then defined multiplicative and completely multiplicative functions and saw that for a multiplicative function f, the value f(1) is either 0 or 1: in the former case, f(n) = 0 for all n, so we will assume that our multiplicative function further satisfies f(1) = 1. 

October 06: Finally proved the fundamental theorem of arithmetic and how to obtain the gcd of two numbers from their respective prime factorizations. Also showed that if the n-th root of an integer is rational, then it was an integer to begin with. HW1 is due on October 08; HW2 has been posted.

October 03: We derived some more consequences of Bezout's lemma: if aX + bY = c has a solution, then c must be divisible by gcd(a, b); if a prime p divides the product ab, then p must divide either a or p must divide b. By induction, the latter also gives that if p divides a product a_1 a_2 a_3 ... a_r, then p must divide one of the a_i. We then stated the fundamental theorem of arithmetic, and began proving it by induction on the number of prime factors in a factorization.

October 01: We saw the key facts which make the Euclidean algorithm work: gcd(a, 0) = a and gcd(a + bq, b) = gcd(a, b) for all integers a, b, and q. We then saw how to use the Euclidean algorithm to obtain Bezout's lemma: given integers a, b, there exists integers r, s such that gcd(a, b) = ra + sb. The integers r and s are often called Bezout coefficients for a and b; they are not unique. We showed that every common divisor of a and b divides gcd(a, b).

September 29: Defined prime integers and divisors. Proved
(i) every integer > 1 has a prime divisor,
(ii) there are infinitely many primes, and
(iii) every integer > 1 has a prime factorization [we do not know yet that this prime factorization is unique!]. 

Then defined the greatest common divisor of two integers and ran the Euclidean algorithm on 54 and 21. Make sure to check carefully that for integers a, b, c, r, s, if a divides both b and c, then a divides rb + sc, and if a divides b and b divides c, then a divides c. 

September 25: Introduction to the course; discussed integral solutions of y^2 = 2^x + 3 in detail.

Lecture Time: MWF 11am to 11:50am
Lecture Location: Peterson Hall Room 102
Textbook: An Introduction to Number Theory, by Harold M. Stark. The MIT Press; Seventh Printing edition. 

Discussion Section:
Section A01: Tu 11am to 11:50am at HSS 4025
Section A02: Tu 12pm to 12:50pm at HSS 4025

Course Personnel:
Instructor: Karthik Ganapathy Venkitachalam
Teaching Assistant: Nathan Wenger
Note: To contact us, please use Piazza. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza.

Office Hours:
Karthik Ganapathy: W 3:30-5:00pm and F 9:30-11:00am at AP&M1230
Nathan Wenger: Tu 1:30-3:30pm in HSS 5029

Homework:
Homework assignments will be posted on Canvas almost every week. Normally you will have one week to submit your completed homework via Gradescope. Your lowest homework assignment will be dropped at the end of the course when computing your grade.

Exam:
There will be two midterm exams and one final exam. No makeup exams will be given in this course.
Note: It is standard Math Department practice to utilize different versions of exams, both within each lecture's exam, and between lectures whose exams are at different times.

Midterm I: 7pm-8pm on October 20 in Warren Lecture Hall 2111.
Midterm II: 7pm-8pm on November 17 in Warren Lecture Hall 2111.
Final exam: 11:30am-2:30pm on December 09 at PETERSON 102.

Regrades: Regrade requests will be made using the built-in regrade request feature in Gradescope. There will be a limited window of time after the exams are made available during which the regrade request feature will be active. This time window will be announced when the exam scores are released. Only the regrade requests sent within the time window will be considered.

Grading Policy:

The grades will be determined as the best of: 

a) 20% Homework, 20% Midterm Exam I, 20% Midterm Exam II, 40% Final Exam; OR

b) 25% Homework, 25% Best Midterm Exam, 50% Final Exam.

Attendance Policy: You are expected to attend every session of the lectures and discussion section you are enrolled in. Students who do not attend class rarely succeed in this course.  If you must miss class for any reason, it is your responsibility to catch up on the material. You are also responsible for the information given in any announcements made during class. To help you with this, I will record every lectures in the event you are unable to attend. Lecture recordings can be found at UCSD Podcast.

Academic Integrity: Academic dishonesty is considered a serious offense at UCSD. Students caught cheating will face an administrative sanction which may include suspension or expulsion from the university. It is in your best interest to take pride in your work maintain your academic integrity.

Accommodations: Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (https://osd.ucsd.edu/.) Students are required to discuss accommodation arrangements with instructors and OSD liaisons in the department in advance of any exams or assignments.

Here are some resources from other UCSD instructors that you may find useful:
1) Cristian Popescu's course website from Winter 2021
2) Aaron Pollack's course website from Winter 2022