Lecture

Modular Arithmetic: Inverses and Equations

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain? ...

Description

This lecture covers modular arithmetic, focusing on inverses and equations in Z/mZ. The instructor explains the solution of the Mod 97-10 procedure, the pigeonhole principle, and theorems related to inverses. Examples and exercises are provided to illustrate the concepts.

Instructors (2)

Bixio Rimoldi

Bixio Rimoldi received the Dipl. El.-Ing degree as well as the Dr. ès Sciences degree from the ETHZ, Switzerland. Since 1997, he holds a full professor position at the School of Computer and Communication Sciences at EPFL and he is the director of EPFL's Mobile Communications Laboratory (LCM). Prior to joining EPFL, he was in the faculty of the Electrical Engineering department of Washington University. In 1993, he received a US National Science Foundation Young Investigator Award. In 2000, he was elected to the grade of Fellow of the IEEE. During the period 2002-2009 he has been on the Board of Governors of the IEEE Information Theory Society, where he served in several offices including President. He was co-chairman with Bruce Hajek of the 1995 IEEE Information Theory Workshop on Information Theory, Multiple Access, and Queueing (St Louis, MO), and co-chairman with Jim Massey of the 2002 IEEE International Symposium in Information Theory (Lausanne, Switzerland). He has been a member of the editorial board of "Foundations and Trends on Communications and Information Theory," and was an editor of the European Transactions on Telecommunications. During 2005 and 2006 he was the Director of EPFL's Bachelor program in Communication Systems. His interests are in various aspects of digital communications, information theory, and software-defined radio.

Michael Christoph Gastpar

Michael Gastpar is a (full) Professor at EPFL. From 2003 to 2011, he was a professor at the University of California at Berkeley, earning his tenure in 2008. He received his Dipl. El.-Ing. degree from ETH Zürich, Switzerland, in 1997 and his MS degree from the University of Illinois at Urbana-Champaign, IL, USA, in 1999. He defended his doctoral thesis at EPFL on Santa Claus day, 2002. He was also a (full) Professor at Delft University of Technology, The Netherlands. His research interests are in network information theory and related coding and signal processing techniques, with applications to sensor networks and neuroscience. He is a Fellow of the IEEE. He is the co-recipient of the 2013 Communications Society & Information Theory Society Joint Paper Award. He was an Information Theory Society Distinguished Lecturer (2009-2011). He won an ERC Starting Grant in 2010, an Okawa Foundation Research Grant in 2008, an NSF CAREER award in 2004, and the 2002 EPFL Best Thesis Award. He has served as an Associate Editor for Shannon Theory for the IEEE Transactions on Information Theory (2008-11), and as Technical Program Committee Co-Chair for the 2010 International Symposium on Information Theory, Austin, TX.

Official source

Related concepts (32)

Modular multiplicative inverse

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as which is the shorthand way of writing the statement that m divides (evenly) the quantity ax − 1, or, put another way, the remainder after dividing ax by the integer m is 1.

Inverse element

In mathematics, the concept of an inverse element generalises the concepts of opposite (−x) and reciprocal (1/x) of numbers. Given an operation denoted here ∗, and an identity element denoted e, if x ∗ y = e, one says that x is a left inverse of y, and that y is a right inverse of x. (An identity element is an element such that x * e = x and e * y = y for all x and y for which the left-hand sides are defined.

Generalized inverse

In mathematics, and in particular, algebra, a generalized inverse (or, g-inverse) of an element x is an element y that has some properties of an inverse element but not necessarily all of them. The purpose of constructing a generalized inverse of a matrix is to obtain a matrix that can serve as an inverse in some sense for a wider class of matrices than invertible matrices. Generalized inverses can be defined in any mathematical structure that involves associative multiplication, that is, in a semigroup.

Multiplicative function

In number theory, a multiplicative function is an arithmetic function f(n) of a positive integer n with the property that f(1) = 1 and whenever a and b are coprime. An arithmetic function f(n) is said to be completely multiplicative (or totally multiplicative) if f(1) = 1 and f(ab) = f(a)f(b) holds for all positive integers a and b, even when they are not coprime.

Modular form

In mathematics, a modular form is a (complex) analytic function on the upper half-plane that satisfies: a kind of functional equation with respect to the group action of the modular group, and a growth condition. The theory of modular forms therefore belongs to complex analysis. The main importance of the theory is its connections with number theory. Modular forms appear in other areas, such as algebraic topology, sphere packing, and string theory.

Related lectures (64)

Fundamental Groups

Explores fundamental groups, homotopy classes, and coverings in connected manifolds.

Modular Arithmetic: Foundations and Applications

Introduces modular arithmetic, its properties, and applications in cryptography and coding theory.

Modular Arithmetic: Operations and Properties

Explains modular arithmetic operations and properties, including commutative rings and multiplicative inverses.

Modular Arithmetic: Introducing Z/mZ

Introduces Z/mZ for writing equations with congruence classes in modular arithmetic.

Calculus of Variations: Some Topics