# Prove that whenever ## ab\equiv cd\pmod {n} ## and....

• Math100
In summary, Proof shows that given that ab and cd are equal modulo n and b and d are also equal modulo n, then d=b-nq. This means that a=c\pmod n.
Math100
Homework Statement
Prove that whenever ## ab\equiv cd\pmod {n} ## and ## b\equiv d\pmod {n} ##, with ## gcd(b, n)=1 ##, then ## a\equiv c\pmod {n} ##.
Relevant Equations
None.
Proof:

Suppose ## ab\equiv cd\pmod {n} ## and ## b\equiv d\pmod {n} ##, with ## gcd(b, n)=1 ##.
Then ## n\mid (ab-cd)\implies nk=ab-cd ## and ## n\mid (b-d)\implies nq=b-d ## for some ## k, q\in\mathbb{Z} ##.
This means ## d=b-nq ##.
Now we substitute ## d=b-nq ## into the equation ## nk=ab-cd ##.
Observe that
\begin{align*}
nk=ab-c(b-nq)\\
nk=ab-bc+cnq\\
nk-cnq=b(a-c)\\
n(k-cq)=b(a-c)\\
nr=b(a-c)\\
\end{align*}
where ## r=k-cq ## is an integer.
Thus ## n\mid [b(a-c)] ##.
Note that ## b\mid m ## if ## b\mid (mn) ## and ## gcd(b, n)=1 ##.
Since ## n\mid [b(a-c)] ## and ## gcd(b, n)=1 ##, it follows that ## n\mid (a-c) ##.
Thus ## a\equiv c\pmod {n} ##.
Therefore, ## a\equiv c\pmod {n} ## whenever ## ab\equiv cd\pmod {n} ## and ## b\equiv d\pmod {n} ##, with ## gcd(b, n)=1 ##.

That's correct.

You used the fact that ##gcd(b,n)=1## is equivalent to the fact that ##b## has a multiplicative inverse modulo ##n## which is equivalent to the fact that ##1=sb+tn## for some integers ##s,t.## Once you have shown these equivalences (##b## and ##n## are coprime, ##b## has an inverse element modulo ##n##, Bézout's lemma: there are ##s,t## such that ##1=sb+tn##), you can use all of them, i.e. the one that fits best.

E.g., since ##b## has an inverse, we get from ##nr=b(a-c)## that ##b^{-1}nr=a-c## and thus ##a-c\equiv 0\pmod n.##

Or, even simpler:
\begin{align*}
gcd(b,n)=1 &\Longrightarrow \exists \,b^{-1} \pmod n \\&\Longrightarrow ab\equiv cd \equiv cb \pmod n\\
&\Longrightarrow a\equiv abb^{-1}\equiv cbb^{-1}\equiv c\pmod n
\end{align*}

You should show that they are equivalent in order to practice proof writing. This can be done e.g. by
##b## and ##n## are coprime ##\Longrightarrow ## there are ##s,t## such that ##1=sb+tn## ##\Longrightarrow ## ##b## has an inverse element modulo ##n## ##\Longrightarrow ## ##b## and ##n## are coprime

Math100
fresh_42 said:
That's correct.

You used the fact that ##gcd(b,n)=1## is equivalent to the fact that ##b## has a multiplicative inverse modulo ##n## which is equivalent to the fact that ##1=sb+tn## for some integers ##s,t.## Once you have shown these equivalences (##b## and ##n## are coprime, ##b## has an inverse element modulo ##n##, Bézout's lemma: there are ##s,t## such that ##1=sb+tn##), you can use all of them, i.e. the one that fits best.

E.g., since ##b## has an inverse, we get from ##nr=b(a-c)## that ##b^{-1}nr=a-c## and thus ##a-c\equiv 0\pmod n.##

Or, even simpler:
\begin{align*}
gcd(b,n)=1 &\Longrightarrow \exists \,b^{-1} \pmod n \\&\Longrightarrow ab\equiv cd \equiv cb \pmod n\\
&\Longrightarrow a\equiv abb^{-1}\equiv cbb^{-1}\equiv c\pmod n
\end{align*}

You should show that they are equivalent in order to practice proof writing. This can be done e.g. by
##b## and ##n## are coprime ##\Longrightarrow ## there are ##s,t## such that ##1=sb+tn## ##\Longrightarrow ## ##b## has an inverse element modulo ##n## ##\Longrightarrow ## ##b## and ##n## are coprime
I like the one you've used under "Or, even simpler:".

fresh_42
Math100 said:
I like the one you've used under "Or, even simpler:".
But it was written a bit sloppy. Better would have been:

\begin{align*}
ab\equiv cd \pmod n \wedge b\equiv d \pmod n &\Longrightarrow ab\equiv cd \equiv cb \pmod n\\
gcd(b,n)=1 &\Longrightarrow \exists \,b^{-1} \pmod n \\
&\Longrightarrow a\equiv abb^{-1}\equiv cbb^{-1}\equiv c\pmod n
\end{align*}

Math100

## 1. What does the notation "ab ≡ cd (mod n)" mean?

The notation "ab ≡ cd (mod n)" means that when the product of two numbers, a and b, is divided by a number n, the remainder is equal to the product of two other numbers, c and d, also divided by n.

## 2. How do you prove that the given statement is true?

To prove that the statement "ab ≡ cd (mod n)" is true, you can use the definition of congruence in modular arithmetic, which states that two numbers are congruent if they have the same remainder when divided by a given number. You can also use the properties of modular arithmetic, such as the distributive property and the fact that the remainder of a product is equal to the product of the remainders.

## 3. Can you provide an example of this statement being true?

Yes, for example, let's say we have the numbers 6, 9, 12, and 15, and we want to prove that 6*9 ≡ 12*15 (mod 3). We can divide each number by 3 and see that the remainders are equal: 6/3 = 2, 9/3 = 3, 12/3 = 4, and 15/3 = 5. Therefore, 6*9 = 18 ≡ 12*15 = 180 (mod 3).

## 4. Is this statement always true?

Yes, this statement is always true in modular arithmetic. In fact, it is one of the fundamental properties of modular arithmetic.

## 5. What are some real-life applications of this statement?

This statement is often used in cryptography and computer science to ensure the security and accuracy of data transmission. It is also used in number theory and algebraic equations to solve for unknown variables and to prove mathematical theorems.

• Precalculus Mathematics Homework Help
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
847
• Precalculus Mathematics Homework Help
Replies
1
Views
976
• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
896
• Precalculus Mathematics Homework Help
Replies
1
Views
971
• Precalculus Mathematics Homework Help
Replies
2
Views
945
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
719