Learn · Introduction to Algebraic Structures
Lecture 56 of 58Week 12 Quadratic residue, Legendre symbol and primes in AP.
More on solving congruence equations and introduction to quadratic residue and Legendre symbol
Prof. Mahesh Kakde and Prof. R. Venkatesh · IISc Bangalore
Credits and licence
- From
- Introduction to Algebraic Structures, IISc Bangalore (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction to mathematics and set theory
- Set identities, Cartesian product, relations and functions
- Logic and construction of new sets
- Functions
- Properties of functions
- Composing functions and Cantor's theorem
- Don Zaiger's proof: Primes of the form 4k+1 can written as sum of two squares.
- Axiom of choice and Paritition of a set.
- Correspondence between partitions of a set and equivalence relations on it.
- Partially ordered sets, well-ordering principle and Zorn's lemma.
- Defining natural numbers: Peano axioms.
- Order properties of natural numbers and notion of cardinality of a set.
- Cardinality of a finite set.
- Countable sets
- Uncountable sets
- Schroder-Bernstein theorem
- Integers and Rational Numbers
- The Construction of Rational Numbers and Counting Principles
- Counting in Two Ways
- Binomial Coefficients and Properties
- The Pigeonhole Principle
- Formal Series
- Formal Series and Applications
- Solving Linear Recurrences
- Principle of Inclusion and Exclusion
- Möbius Function on Finite Posets
- Möbius Inversion Formula
- Möbius Inversion Formula and Applications
- Introduction to Graph Theory, Graphs and Special Graph Families
- Graph Representations and Basic Graph Operations
- Handshake Lemma and Graph Connectivity
- Cycles, Bipartite Graphs, and Trees
- Trees and Their Properties
- Eulerian and Hamiltonian Graphs
- Matchings and Graph Coloring
- Number theory and divisibility
- Greatest Common Divisor - I
- Greatest Common Divisor - II
- LCM, primes and prime factorisation
- Consequences of prime factorisation and infinitude of primes
- Euler's proof of infinitude of primes
- Congruencies and modular arithmetic
- Diophantine equations and residue classes
- Solving Diophantine equations in one variable and Chinese remainder theorem
- Solving Diophantine equations using CRT
- Proof of Hensel's lemma
- Introduction to Euler's totient function
- More on totient function
- Mobius inversion formula
- Euler's theorem
- Ring structure on set of residue classes
- Polynomial ring over a field, division algorithm and consequences.
- Wilson's theorem, Lagrange's theorem and introduction to cyclic groups
- Classification of cyclic unit groups modulo m and proof.
- Primitive roots modulo m and application in solving linear congruences
- More on solving congruence equations and introduction to quadratic residue and Legendre symbol
- Computing Legendre symbol: Euler's criterion and Law of quadratic reciprocity
- Dirichlet's theorem on primes in AP: Proof of special cases