DISCRETE CHECKING FOR MODULAR CONGRUENCE Please Please Pleas

DISCRETE :CHECKING FOR MODULAR CONGRUENCE

Please Please Please show ALL WORK and als PROVIDE Theorems , definitions and explanations for all steps!

TY

Solution

Congruence Modulo

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 any integers a and b, and positive integer n, we have:

a a mod n.

If a b mod n then b a mod n.

If a b mod n and b c mod n then a c mod n

These results are called: Reflexivity, Symmetry and Transitivity.

The proof : 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|(ba) and n|(cb). Using the linear combination theorem, we have n|(b a + c b) or n|(c a). Thus, a c mod n.

If a b mod n then b = a + nq for some integer q, and conversely.

Proof: If a b mod n then by definition n|(b a). Therefore, b a = nq for some q. Thus b = a+nq. Conversely if b = a+nq, then ba = nq and so n|(ba) and hence a b mod n then b = a + nq.

If gcd(a, n)=1, then the congruence ax b mod n has a solution x = c. In this case, the general solution of the congruence is given by x c mod n.

Proof: Since a and n are relative prime, we can express 1 as a linear combination of them: ar + ns = 1 Multiply this by b to get abr + nbs = b. Take this mod n to get abr + nbs b mod n or abr b mod n Thus c = br is a solution of the congruence ax b mod n. In general, if x c mod n we have ax ac b mod n. We now claim that any solution of ax b mod n is necessarily congruent to c mod n. For suppose ax b mod n. We already know that ac b mod n. Subtract to get ax ac 0 mod n or a(x c) 0 mod n But this means that n|a(x br). But since a and n are relatively prime, this implies that n|(x c) and x c mod n.

AB(mod C)

This says that A is congruent to B modulo C

Let\'s imagine we were calculating mod 5 for all of the integers:

Suppose we labelled 5 slices 0, 1, 2, 3, 4. Then, for each of the integers, we put it into a slice that matched the value of the integer mod 5.
Think of these slices as buckets, which hold a set of numbers. For example, 26 would go in the slice labelled 1, because 26 mod 5=1.
A common way of expressing that two values are in the same slice, is to say they are in the same equivalence class.

mathematically   AB (mod C)