Monday 26 January 2015

elementary number theory - Why is modular inverse notation so ambiguous?



Consider



$$\frac{a}{a}\pmod a,\ \ \ a\in\mathbb Z\setminus\{-1,0,1\}$$



There are two cases:




$1)$ $\frac{a}{a}$ is the notation for the real number $1$.
Then the expression is equivalent to $1$ modulo $a$.



E.g., see this, where the expression on the LHS would not even exist if what would be meant by $99$ in the denominator is modular inverse instead of regular integer division.



$2)$ $\frac{a}{a}$ is the notation for $ax$, where $x$ is in the class of solutions to $ax\equiv 1\pmod{a}$.
Since $x$ does not exist, $\frac{a}{a}$ does not exist too in this case.



So $\frac{a}{a}\mod a$ can be thought of as either equivalent to $1$ modulo $a$ or not existing at all.



Now, $aa^{-1}$ is possibly more commonly used than $\frac{a}{a}$ in modular arithmetic and $\frac{a}{a}$ is more commonly used than $aa^{-1}$ in division in integers, but surely not always.




Such notation was probably created due to its similarities to division in integers, but I think less ambiguous notation should've been created instead.



Also see this.
There's a comment there that points out my problem. Consider:



$$\frac{ac}{bc}\pmod m,$$



where $$\gcd(b,m)=1,\ \ \ \gcd(c,m)>1,\ \ \ m\in\mathbb Z\setminus\{-1,0,1\},\ \ \ c\in\mathbb Z\setminus\{0\},\ \ \ b\in\mathbb Z\{0\},\ \ \ a\in\mathbb Z$$



can either be equivalent to $\frac{a}{b}\pmod{m}$ if the fractional notation denotes integer division or it could not exist at all if the fractional notation denotes modular inverses.



Answer



First, a simple example: note that $\, 1+2+\cdots +n\, =\,\dfrac{n(n+1)}2\ $ remains true modulo $\,2,\,$ but it would be more cumbersome to state without the very convenient fractional notation.



Let's consider an analogous but simpler example of the question in your first link, namely
$\qquad {\rm mod}\ 9\!:\ \ \dfrac{10^n-1}9\, =\, \overbrace{\color{#c00}{11\cdots 11}}^{\large n\ 1's} \,\equiv\, n\ $ by $10\equiv 1,\,$ i.e. by casting out nines



Here, the context is congruences on integers, so the fraction denotes an $\rm\color{#c00}{integer,}$ viz. the integer obtained by cancelling $\,9\,$ from the fraction. The mod applies to that integer. More generally



$\qquad {\rm mod}\ x\!-\!a\!:\ \ \dfrac{f(x)-f(a)}{x-a} \equiv\, f'(a)$




Here the context is polynomials over some ring, so the fraction denotes the unique polynomial obtained by the division (which is exact by the Factor Theorem). This yields a purely algebraic definition of polynomial derivatives.



In all cases, the fraction can be considered to be a convenient notation used to denote a certain element $\,r\,$ of the ambient ring. The notation proves convenient because it conveys information about the ring-theoretic properties of that element, e.g. in the first example above it denotes the (unique!) solution of $\ 9r = 10^n-1\,$ in $\,\Bbb Z.$



Such (universal) cancellation (before evaluation) can prove quite powerful, e.g. we can prove Sylvester's determinant identity $\rm\,\det(1+AB) = \det(1+BA)\,$ by computing the determinant of $\rm\ (1+A\ B)\ A\ =\ A\ (1+B\ A)\ \ $ then cancelling $\rm\ det(A),\,$ all done in $\,\Bbb Z[a_{ij}],\,$ where the matrix entries are indeterminates. Similarly one can compute the adjugate of the adjugate. Beware: it can be perplexing at first glance, esp. understanding why the proof works even when $\,\rm\det(A) = 0.$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...