Congruent Modulo n

In general, in many books for Quantitative Mathematics, this chapter various number theories is not found with detailed explanations and it is an established fact that if you are well-conversant with number theories, you can do these questions within a very short time and further sometimes without writing a word on paper. For example, see these questions that appeared in CAT/ CSAT/ CLAT or in any other competitive exam:

Hence, I have given special emphasis on this chapter to instill a confidence in CAT aspirants in terms of doing such questions with accuracy and precisions within strict timelines.

The objectives of this chapter, apart from giving you a good insight into Modular Arithmetic, include an introduction to Fermat’s Little Theorem, Euler’s Function and Wilson Theorem to equip the students with classic tools of solving some tough problems of Number Theory with complete ease.

The objective of this chapter is to explain to you various number theories in most subtle way so that even a novice can understand it. Hence, I have included a complete section on theory part coupled with "easy-to-understand" conceptual lessons, and of course, with a lot of examples.

To understand the idea behind Perception of Modular Arithmetic, you may study my blog on this website.

Definition of Congruent Modulo n: For a positive integer n, two integers a and b are said to be congruent modulo n, if their difference (a – b) is divisible by a positive integer n, or in other words, is difference (a – b) is an integral multiple of n. We may say that there exists an integer k, such that a − b = kn.

This congruence relation is denoted by a ≡ b mod n. ……. (1)

(Note: For showing congruence relation, the signs == and ≡ have been used interchangeably.)

The only difference between a = kn + b {(i.e. a = b+ kn arising out of a ≡ b (mod n) and c = dq+r (typical division algorithm) is that b may not be the remainder of the division of a by n in the sense that 0 <= b < n, i.e, b may not be belonging to the set {0, 1, 2, …., (n-1)}.

Look at the example,

22 ≡ 6 mod 2. But 22 is not the remainder when 6 is divided by 2. We can apply this rule, as will be clearer to you as we go ahead, for negative integers also, but remember, the n, i.e. the divisor shall always be a positive integer.

The arithmetical analogy of (1) above is in division algorithm. This statement (1) is equal to saying: a = b+ kn, and precisely a = kn + b in harmony with typical way of writing division algorithm c = dq+r, where c is dividend, d is divisor, q is quotient and r is remainder, 0 ≤.r< d)

Another very corollary to a ≡ b (mod n) is that remainder (a, n) = remainder (b, n)

See this example:

27 ≡ 13 mod 7 {Both 27 and 13, when divided by 7, leave the same reminder, i.e. 6.}; And-36 ≡ 12 mod 8 {Both -36 and 12, when divided by 8, leave the same reminder, i.e. 4}

How does the number -36 leave remainder 4 when divided by 8?

As for remainders, what you are looking for when you divide -36 by 8 is a quotient q and a POSITIVE remainder r (less than 8) such that -36 = 8q + r

Conceptually, that means that you need to subtract from -36 the greatest multiple of 8 that is LESS than -36, which is -40 (Remember, remainder must be a positive integer), i.e. r = -36 - 8(-5) = -36 - -40 = 4

So we can say that -36 == 12 (mod 8) because 12 – (-36) = 48 is a multiple of 8.

-36 ≡ 12 mod 8 {Both -36 and 12, when divided by 8, leave the same reminder, i.e. 4}. But how does the number -36 leave remainder 4 when divided by 8?

As for remainders, what you are looking for when you divide -36 by 8 is a quotient q and a POSITIVE remainder r (less than 8) such that -36 = 8q + r.

Means, -36 = {8x(-5)} + 4. Conceptually, that means that you need to subtract from -36 the greatest multiple of 8 that is LESS than -36, which is -40:

You may visit my blog "Equivalence Class in Congruent Modulo".

NOTE: Further, for example, 33 == 7 mod 13 means that 33 and 7 are congruent modulo 13, because the difference between 33 and 7 is divisible by 13, and because both 33 and 7, when divided by 13, leave the same remainder, i.e. 7. Some other numbers with divisor being 7 are 2, 9, 16, .. We shall say these numbers are congruent to each other modulo 7, and write 16 == 9 == 2 (mod7).

And of course, understand a VERY basic feature from these examples:

69 == 47 mod 11; hence 69 == 3 mod 11 as 47 == 3 mod 11

121 == 52 mod 23; hence 121 == 6 mod 23

93 == 23 mod 7; hence, 93 == 2 mod 7

.

This is: if a == b mod n and b>n, then, a == c mod n where c is the remainder when b is divided by n.

Example 01

The algebra of congruent modulo n has been explained at my blog "Algebra of Congruent Modulo n"

Example 02: A certain number on dividing by 899 gives a remainder 63. What shall be the remainder when same number is divided by 29? A. 5 B. 25 C. 27 D. 28

Sol: Since the given number on dividing by 899 gives a remainder 63, we may write the number, say P, as: P == 63 mod 899.

This may, for some positive integer M, be written further as; P = 899M + 63. This may further be written as: P = (29x31)M + {(29x2) + 5}. Obviously, 5 is the required remainder, as: P = 29x{(31M + 2)} + 5

See this example. Suppose, you divide 15 by 7, you have remainder 1, and you can always write it in terms of Euclid Division Algorithm, as:

15 = (2x7) + 1. Though the remainder is always a positive integer, you can always think it writing like this too: 15 = (3x7) + (-6).

And this can be written as: 15 == -6 mod 7. This idea is wonderful in solving many questions. Some have been solved here.

Example 04: A number when divided by 3 leaves a remainder 1. When the quotient is divided by 2, it leaves a remainder 1. What will be the remainder when the number is divided by 6? A. 2 B. 3 C. 4 D. 5

Sol: Let the number be N. Then, as given, N = 3Q + 1. Further given,

Q = 2Y + 1. These two equations give: N = 6Y + 4.

Obviously, 4 is the required remainder.