Intereting Posts

Alternate Proof for $e^x \ge x+1$
complement of zero set of holomorphic function is connected
What's the deal with empty models in first-order logic?
$\displaystyle\sum_{k=0}^n \frac{\cos(k x)}{\cos^kx} = ?$
An inequality on holomorphic functions
variance inequality
What is the definition of limit superior/inferior of real function?
Is $SL_n(\mathbb{R})$ a normal subgroup in $GL_n(\mathbb{R})$?
Approximation of conditional expectation
Set theory: cardinality of a subset of a finite set.
Rigid motion on $\mathbb{R}^2$ which fixes the origin is linear
Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $
Is this equality true or it is not necessarily true?
Existence theorem for antiderivatives by Weierstrass approximation theorem
Gradient of a function restricted to a submanifold

Prove that if $a\equiv b \pmod m$ , then

$a \bmod m = b \bmod m$

Given,

$a\equiv b \pmod m$

- How many essential ways: $n$ balls in $k$ bins, where $k$ can vary and there are $\geq 2$ balls in each bin?
- Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves?
- Increase by one, Shortest path, changes the edges or not?
- What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's?
- Complex Permutation
- Which non-Abelian finite groups contain the two specific centralizers? - part II

$\implies m\mid (a-b)$

$\implies (a-b)=m\cdot k$

$\implies a=b+m\cdot k$

Now,

$a \bmod m$ can be written as

$\implies b+m\cdot k \pmod m$

No idea how to move forward to get

$$b \pmod m \impliedby b +m\cdot k \pmod m$$

Please help me out!!!

Thanks!

- How can this English sentence be translated into a logical expression?
- The locker problem - why squares?
- Determine whether $712! + 1$ is a prime number or not
- Ordered binary sequences of length n with no two consecutive 0's without using recursion
- Solution to exponential congruence
- Prime of the form $4p+1$
- Coloring dots in a circle with no two consecutive dots being the same color
- Infinitely many systems of $23$ consecutive integers
- Motivation behind the definition of GCD and LCM
- Find remainder of $F_n$ when divided by $5$

$$a\equiv b \pmod m$$

$$\implies (a-b) = m k $$

$$\implies a = m k + b $$

$$\implies a \bmod m = (mk\bmod m + b\bmod m)\bmod m = b\bmod m \bmod m = b \bmod m$$

$$\implies a \bmod m = b \bmod m$$

Here is an important point raised by @(Bill Dubuque) in this proof. In line $4$, I used $(mk+b)\bmod m = (mk\bmod m + b\bmod m)\bmod m$ which must be proved for the completion of the proof of the original result. There are multiple ways to prove this equality, however if one uses the approach used in this answer, then this leads to a circular dependency i.e. usage of this equality to prove the original result and the usage of the original result in proving this equality. So, to complete the proof of original result one must prove this equality with some other approach. Based on the suggestion by Bill, **here is a revised proof**,

Let $b = mq + r \implies b \bmod m = r$, then,

$$a\equiv b \pmod m$$

$$\implies (a-b) = m k $$

$$\implies a = m k + b = mk + mq + r = m(k+q) + r $$

$$\implies a \bmod m = r = b \bmod m$$

$$\implies a \bmod m = b \bmod m$$

**Note:**

Here is an issues found by @(Bill Dubuque) in my first proof.

$$a\equiv b \pmod m$$

$$\implies (a-b) = m k $$

$$\implies (a-b)\bmod m = m k \bmod m $$

$$\implies a \bmod m – b \bmod m = 0$$

$$\implies a \bmod m = b \bmod m$$

But the $4$th equation above cannot follow from the $3$rd equation in general (counterexample $a=m$ and $b=1$).

**Hint** $\, $ Show $\ c\equiv d\pmod{\!m}\,$ and $\,|c-d|<m\,\Rightarrow\, c= d$

Apply that to $\,\ \underbrace{a\bmod m}_{\Large c}\!\equiv a\equiv b\equiv \underbrace{b\bmod m}_{\Large d}\,\ \pmod{\!m}$

**Remark** $ $ Any sequence of $m$ consecutive integers forms a complete system $S$ of representatives (*normal forms*) of all equivalence classes mod $m,\,$ so the above implies that congruence reduces to *equality* on these normal forms, i.e. $\ a\equiv b\iff \bar a = \bar b,\,$ where $\bar n =$ unique normal-form rep in $S$ congruent to $n\,$ (which is analogous to: $ $ fractions are equivalent iff their least form rep’s are *equal*, i.e. *least terms* fractions are normal forms for equivalence of fractions).

An alternative convenient choice of normal forms for modular arithmetic arises by choosing the *least magnitude* reps (signed or balanced residue system), e.g. $\,\{-2,\color{#c00}{-1},0,1,2\}\pmod{\! 5}.\,$ In these signed systems the normal form of $\,m\!-\!1\,$ is $\,-1,\,$ e.g. above $\,4\equiv\color{#c00}{-1}\pmod{\!5},\,$ simplifying common calculations such as $\,(m\!-\!1)^k\equiv (-1)^k,\,$ e.g. when casting out elevens.

The phrase $a \mod m$ as some specific numerical value is not a universally understood or accepted concept and so the phrase $a \mod m = b\mod m$ may not have any sensible meaning depending on which mathematician you ask.

It *can* be taken to mean: For any $m \in \mathbb N$ (not including 0) and any integer $a$ there will exist unique integers $q, r$ so that $a = qm + r$ and $0 \le r < m$. We define $r$ as the *remainder* where $a$ is divided by $m$.

I have *seen* this called $r = a \mod m$ or more commonly $r = a \% m$. In my opinion, I can accept the latter if it is properly defined but I detest the former as it is an abuse of notation and concept.

The notation $a \equiv b \mod m$ means $m$ divides $a- b$ or equivalently $a$ and $b$ have the same remainder when divided by $m$. But the important thing is that this is not a statement about specific integers– it is a statement about **equivalence classes** of sets of integers. $a \equiv b \mod m$ mean that both $a$ and $b$ are elements of the the same set $M = \{ x\in \mathbb Z| m|(x-a)\}$.

Anyway. Assuming that you mean $a \mod m$ to mean the unique integer remainder as I desribed in the second paragraph then the proof is trivial:

Suppose $a \equiv b \mod m$ Let $r_1 = a \mod m$ so $a = jm + r_1$ or $r_1 = a = jm$ for some integer $j$ and let $r_2 = b \mod m$ so $b = lm + r_2$ o $r_2 = b- lm$ and $0 \le r_1 < m; 0 \le r_2 < m$. So $r_1 – r_2= (a-b) + (j- l)m$ So as $m|(a-b)$ and $m|(j-l)n$ then $m|r_1 – r_2$.

Let $r_1 – r_2 = dm$ for some integer $d$.

then $m > r_1 > r_1 – r_2 = dm$ and $dm = r_1 – r_2 > -r_2 > m$ so $m > dm > -m$ and $1 > d > -1$ but $d$ is an integer.

So $d= 0$ and $r_1 – r_2 = 0*m = 0$ and $a \mod m = r_1 = r_2 = b \mod m$.

Write $a=qm+r$ and $b=pm+s$, where $0\leq s,r<m$.

Then $a\;\underline{mod}\;m = r$ and $b\;\underline{mod}\;m = s$. On the other hand, $a\equiv b\; mod \;m$ iff $m|a-b$ iff (above) $m|r-s$ iff ($r,s$ remainders) $r=s$.

I think it’s obvious:

You have that $a \equiv b+mk \pmod m$.

But, $mk \equiv 0 \pmod m$ , so $a \equiv b+mk \equiv b\pmod m$.

Done.

- Why $\mathbf{0}$ vector has dimension zero?
- Determinant of circulant matrix
- Does the equation has a non-trivial solution?
- Deriving the transformation function of a random variable from the original and the final distributions
- Why square matrix with zero determinant have non trivial solution
- Transformation outside injectivity 'domain' in Int. by substitution ok? And outside the integration interval?
- Question about the proof that a countable union of countable sets is countable
- Equivalence of two characterizations of the norm of an algebraic integer.
- Is there a domain which is not UFD but has a maximal principal ideal?
- equivalence between uniform and normal distribution
- Finding all solutions of $x^{11}\equiv 1\bmod23,$
- Prove functions defined by sup and inf are continuous
- Modulo of sum of random variables
- Can contractible subspace be ignored/collapsed when computing $\pi_n$ or $H_n$?
- Gnarly equality proof? Or not?