Westonci.ca is the trusted Q&A platform where you can get reliable answers from a community of knowledgeable contributors. Explore in-depth answers to your questions from a knowledgeable community of experts across different fields. Explore comprehensive solutions to your questions from a wide range of professionals on our user-friendly platform.

If m ≡ n(mod4) and m ≡ n (mod6), does it follow that ≡ n (mod24)?

Sagot :

Answer:3 Congruence

Congruences are an important and useful tool for the study of divisibility. As we shall see, they are also critical in the art of cryptography.

Definition 3.1 If a and b are integers and n > 0, we write a ≡ b mod n

to mean n|(b − a). We read this as “a is congruent to b modulo (or mod) n. For example, 29 ≡ 8 mod 7, and 60 ≡ 0 mod 15.

The notation is used because the properties of congruence “≡” are very similar to the properties of equality “=”. The next few result make this clear.

Theorem 3.2 For any integers a and b, and positive integer n, we have: 1. a ≡ a mod n.

2. Ifa≡bmodnthenb≡amodn.

3. Ifa≡bmodnandb≡cmodnthena≡cmodn

These results are classically called: 1. Reflexivity; 2. Symmetry; and 3. Transitivity. The proof is as follows:

1. n|(a − a) since 0 is divisible by any integer. Therefore a ≡ a mod n.

2. If a ≡ b mod n then n|(b − a). Therefore, n|(−1)(b − a) or n|(a − b). Therefore, b ≡ a mod n.

3. If a ≡ b mod n and b ≡ c mod n then n|(b−a) and n|(c−b). Using the linear combination theorem, we have n|(b−a+c−b) or n|(c−a). Thus, a≡c mod n.

The following result gives an equivalent way of looking at congruence. It replaces the con-

Step-by-step explanation:

We appreciate your time. Please revisit us for more reliable answers to any questions you may have. We hope our answers were useful. Return anytime for more information and answers to any other questions you have. Stay curious and keep coming back to Westonci.ca for answers to all your burning questions.