can anyone tell me about congruence in number theory ?...in number theory only
Answers
Answer:
As with so many concepts we will see, congruence is simple, perhaps familiar to you, yet enormously useful and powerful in the study of number theory. If n is a positive integer, we say the integers a and b are congruent modulo n, and write a≡b(modn), if they have the same remainder on division by n. (By remainder, of course, we mean the unique number rr defined by the Division Algorithm.) This notation, and much of the elementary theory of congruence, is due to the famous German mathematician, Carl Friedrich Gauss—certainly the outstanding mathematician of his time, and perhaps the greatest mathematician of all time.
Step-by-step explanation:
Example 3.1.1 {…,−6,1,8,15,…}{…,−6,1,8,15,…} are all congruent modulo 7 because their remainders on division by 7 equal 1. {…,−4,4,12,20,…}{…,−4,4,12,20,…} are all congruent modulo 8 since their remainders on division by 8 equal 4.
Here is a wonderfully useful result.
Lemma 3.1.2 a≡b(modn)a≡b(modn) if and only if n|(a−b)n|(a−b).Proof : We break the proof into two parts: (only if) If a≡b(modn)a≡b(modn), then there are integers qq, q′q′ and rr, with a=qn+ra=qn+r and b=q′n+rb=q′n+r. So a−b=(qn+r)−(q′n+r)=(q−q′)na−b=(qn+r)−(q′n+r)=(q−q′)n, which means n|a−bn|a−b. (if) Suppose n|a−bn|a−b, so there is an xx with a−b=xna−b=xn, that is, a=b+xna=b+xn. Suppose rr is the remainder on dividing nn into bb; we need to show that rr is also the remainder on dividing nn into aa. Since b=qn+rb=qn+r, we have a=b+xn=qn+r+xn=(q+x)n+ra=b+xn=qn+r+xn=(q+x)n+r. Thus, when nn is divided into aa, the remainder is rr as desired. If the value of nn is clear from the context, we often write simply a≡ba≡b. Congruence of integers shares many properties with equality; we list a few here.Theorem 3.1.3 Congruence modulo nn satisfies the following:
1. a≡aa≡a for any aa;
2. a≡ba≡b implies b≡ab≡a;
3. a≡ba≡b and b≡cb≡c implies a≡ca≡c;
4. a≡0a≡0 iff n|an|a;
5. a≡ba≡b and c≡dc≡d implies a+c≡b+da+c≡b+d;
6. a≡ba≡b and c≡dc≡d implies a−c≡b−da−c≡b−d;
7. a≡ba≡b and c≡dc≡d implies ac≡bdac≡bd;
8. a≡ba≡b implies aj≡bjaj≡bj for each integer j≥1j≥1. Proof : Parts 1, 2, 3 and 4 are clear by the definition of congruence. (Aren't they? Check!) We'll prove parts 6 and 8, leaving parts 5 and 7 as exercises. Part 6: By hypothesis n|a−bn|a−b and n|c−dn|c−d, so we have n|(a−b)−(c−d)n|(a−b)−(c−d). Rearranging the terms, this means n|(a−c)−(b−d)n|(a−c)−(b−d), so a−c≡b−da−c≡b−d. Part 8: This follows from part 7, but it is easy to prove it directly: since a≡ba≡b, n|a−bn|a−b. Therefore,
n|(a−b)(aj−1+aj−2b+…+abj−2+bj−1)=aj−bj,
n|(a−b)(aj−1+aj−2b+…+abj−2+bj−1)=aj−bj,
so aj≡bjaj≡bj. Be sure you notice how often we have used lemma 3.1.2. Parts 5–8 can be summarized by saying that in any expression involving +,−,⋅+,−,⋅ and positive integer exponents (that is, any "polynomial''), if individual terms are replaced by other terms that are congruent to them modulo nn, the resulting expression is congruent to the original.