Search the corpus

    Congruence modulo a polynomial is an equivalence relation

    E-HK-45-5

    Area
    Algebra
    Topics
    Polynomial Ideals, Polynomials
    Status
    draft

    Prove, for any non-zero polynomial \(p\), that congruence modulo \(p\) is an equivalence relation.

    1. It is reflexive: \(f \equiv f \bmod p\).

    2. It is symmetric: if \(f \equiv g \bmod p\), then \(g \equiv f \bmod p\).

    3. It is transitive: if \(f \equiv g \bmod p\) and \(g \equiv h \bmod p\), then \(f \equiv h \bmod p\).

    Solution

    By definition, \[ f\equiv g\pmod p \] means that \(p\) divides \(f-g\).

    1. Since \(f-f=0\) and \(p\mid0\), we have \(f\equiv f\pmod p\).

    2. If \(p\mid(f-g)\), then \[ g-f=-(f-g), \] so \(p\mid(g-f)\) and hence \(g\equiv f\pmod p\).

    3. If \(p\mid(f-g)\) and \(p\mid(g-h)\), then \[ f-h=(f-g)+(g-h), \] so \(p\mid(f-h)\). Hence \(f\equiv h\pmod p\).

    Thus congruence modulo \(p\) is an equivalence relation.

    Source Collections