Math 105 (Fall 2025)

October 29: 

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