Anki Deck Changes

Commit: 73e0626a - add explanation to gcd > 1 thus no inverse

Author: obrhubr <obrhubr@gmail.com>

Date: 2025-12-18T07:21:30+01:00

Changes: 1 note(s) changed (0 added, 1 modified, 0 deleted)

Note 1: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: g|p?@3JwCd
modified

Before

Front

ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses
Why does \(ax \equiv_m 1\) have no solution when \(\text{gcd}(a, m) = d > 1\)?

Back

ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses
Why does \(ax \equiv_m 1\) have no solution when \(\text{gcd}(a, m) = d > 1\)?
If \(d | a\) and \(d | m\), then \(d | ax\) for any \(x\). But \(d \nmid 1\), so \(ax\) can never be congruent to \(1\) modulo \(m\).

See bezouts identity on why there is no solution ax - ym = 1.

After

Front

ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses
Why does \(ax \equiv_m 1\) have no solution when \(\text{gcd}(a, m) = d > 1\)?

Back

ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses
Why does \(ax \equiv_m 1\) have no solution when \(\text{gcd}(a, m) = d > 1\)?
We can rewrite \(ax \equiv_m 1\) as \(ax - 1 = km \Leftrightarrow ax - km = 1\). Now since, \(d | a\) and \(d | m\), then \(d | ax\) and \(d | km\) for any \(x\).
Thus \(d | (ax - km)\), and \(ax - km = 1\).

But \(d \nmid 1 \implies d \nmid (ax - km)\), which is a contradiction. Thus \(ax\) can never be congruent to \(1\) modulo \(m\).
Field-by-field Comparison
Field Before After
Back If \(d | a\) and \(d | m\), then \(d | ax\) for any \(x\). But \(d \nmid 1\), so \(ax\) can never be congruent to \(1\) modulo \(m\).<br><br>See bezouts identity on why there is no solution ax - ym = 1. We can rewrite&nbsp;\(ax \equiv_m 1\)&nbsp;as&nbsp;\(ax - 1 = km \Leftrightarrow ax - km = 1\). Now since,&nbsp;\(d | a\)&nbsp;and \(d | m\), then \(d | ax\)&nbsp;and&nbsp;\(d | km\)&nbsp;for any \(x\).<br>Thus&nbsp;\(d | (ax - km)\), and&nbsp;\(ax - km = 1\).<br><br>But \(d \nmid 1 \implies d \nmid (ax - km)\), which is a contradiction. Thus&nbsp;\(ax\) can never be congruent to \(1\) modulo \(m\).
Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses
↑ Top