0

If $a \equiv b \pmod n$ and if $d \mid n$, then $a \equiv b \pmod d$

It is simple as just need the divisibility based relation, $n = dk, \exists k \in \mathbb{Z}$.
As, $a - ln = b - mn, \exists l,m \in \mathbb{Z}$, so for any factor $d$ of $n$ it should also hold true, i.e. :
$a - lkd = b - mkd, \exists k,l,m \in \mathbb{Z}$.

My issue is should the difference be in terms of $lkd, mkd$ only, or something else is also possible. Any small working example will show that only $lkd, mkd$ are the correct choices.

jiten
  • 4,524
  • 1
    $lkd,mkd$ are the differences of what? – user_194421 Jan 19 '18 at 09:23
  • They can be positive, negative as comprise both types of integers, or they can be zero even, it all depends on the value of $a, b$ and the need for them to be in the same equivalence class w.r.t. $n$. So, they can be addition, subtraction, or nothing; just to make them in the same congruence class w.r.t. $n$. – jiten Jan 19 '18 at 09:26
  • 2
    You really ought to put the quantifiers (like $\exists$) before the relation they modify. So instead of $n = dk, \exists k \in \mathbb{Z}$, use $\exists k \in \mathbb{Z}, n = dk$. I know that when we use regular human language, we may say something like "$n = dk$ for some integer $k$", but once you use actual quantifier symbols it looks very strange. – Arthur Jan 19 '18 at 09:27
  • I also felt that logically many times, but could not decide. Thanks for that. – jiten Jan 19 '18 at 09:28
  • 1
    As for the answer, can't you use $lkd-1,mkd-1$? – user_194421 Jan 19 '18 at 09:34
  • @user_194421 No, I am correct, as we assume there exist integers $lk, mk$ s.t. there is no need for any $s_1, s_2$; as shown below by your logic the correct answer is $\exists l,k,d, s_1, s_2 \in \mathbb{Z}$, s.t. $lkd - s_1, mkd -s_2, 0\le s_1, s_2 \lt d$, as just need the same equivalence class. – jiten Jan 19 '18 at 09:35
  • 1
    Did you mean $mkd$? – user_194421 Jan 19 '18 at 09:37
  • Yes, that was a typo. – jiten Jan 19 '18 at 09:38
  • @user_194421 Even better, we assume there exist integers $l, m$ s.t. there is no need for any $s_1, s_2$. It is implicit in the defn. of finding such multiples. – jiten Jan 19 '18 at 09:42
  • 1
    @jiten If then yes, the differences are in the form $lkd,mkd$, because of a corollary of the original assumption: $n|a-b$. – user_194421 Jan 19 '18 at 09:42
  • @user_194421 I would say that the corollary is based on two assumptions: (i) $d \mid n$, (ii) $n\mid (a-b)$. – jiten Jan 19 '18 at 09:45
  • 1
    @jiten Oh, yes, I forgot. – user_194421 Jan 19 '18 at 09:46
  • Thanks for the discussion. – jiten Jan 19 '18 at 09:46
  • 1
    @jiten You're welcome. – user_194421 Jan 19 '18 at 09:47
  • @user_194421 I feel you have given a very good answer when you said that : $lkd-1, mkd-1$ can also be used. In fact, the entire set of $d$ values can be taken, for each value of $l,m$. This is a very good answer indeed, an eye-opener. Also, this can be for all divisors $d_i$ of $n$, where $\prod d_i = n$. Again for each $d_i$ there can be an infinite set of values (for a particular set of value $l_i, m_i$ found by EEA) given by: ${l_i +\frac{td_i}{(a,d)}, m_i+\frac{td_i}{(b,d)}}$. I feel that this is getting long, and have posted a new OP at: https://math.stackexchange.com/q/2612433/424260 – jiten Jan 19 '18 at 17:32
  • @user_194421 I feel you have given a very good answer when you said that : $lkd-1, mkd-1$ can also be used. The entire set of $d$ values can be taken, for each value of $l,m$. Also, for all divisors $d_i$ of $n$, where $\prod d_i = n$. Again for each $d_i$ there is infinite set of values (for particular values $l_i, m_i$ found by EEA) given by: ${l_i +\frac{td_i}{(a,d_i)}, m_i+\frac{td_i}{(b,d_i)}}$, where $(a,d_i) = $ gcd of $a, d_i$ and similarly for $(b,d_i)$. In each of these infinite solutions, there are $d_i$ in-congruent solutions. Similarly for each of the $p$ factors of $n$. – jiten Jan 19 '18 at 18:11
  • @user_194421 Please find a trimmed down version of the deleted OP at: https://math.stackexchange.com/questions/2612532/number-of-solutions-of-a-equiv-b-pmod-m – jiten Jan 19 '18 at 18:50
  • @user_194421 I hope your comment regarding $lkd -1, mkd -1$ being a solution, referred to an in-congruent solution among the $d$ solutions possible. Hence, the answer to your question is : no; as there are for a given congruent solution given by a set of values $k,l$, $d-1$ in-congruent solutions lying in different residue classes. – jiten Jan 19 '18 at 19:13
  • @user_194421 Please just vet my earlier comment. – jiten Jan 19 '18 at 19:41

0 Answers0