Number Theory Help!....will give 10 points?
Prove or Disprove: for any integer a, the congruence expression a ≡ a (mod m) always holds.
Can you write the proof out and explain why? I am so confused!
- 9 years agoFavorite Answer
Definition: We say a | b or a divides b if there exists an integer k such that ak = b.
Definition: We say a = b (mod m) if m | (a - b)
Lemma: x | 0 for any non-zero number x.
Proof: Let x =/= 0. We need to show that x | 0. We need to show that there exists an integer k such that xk = 0. Take k = 0. Then xk = 0 holds since xk = x*0 = 0.
By the Lemma, m | 0 for any non-zero number m. Then since a - a = 0 we see that m | (a - a). Then by definition, m | (a - a) implies that a = a (mod m). Thus, a = a (mod m) holds!
- lotus496Lv 49 years ago
In elementary number theory, the notion of congruence is defined as follows:
a ≡ b (mod m) if and only if m divides (a - b).
[It is assumed that the integer m (called the modulus) is non-zero.]
[We say that x divides y if we can write y as a multiple of x so that y = kx for some integer k. For example 2 divides 10 because 10 = 5(2). In other words 10 is evenly divisible by 2.]
So we have,
a ≡ a (mod m)
if and only if m divides (a - a)
if and only if m divides 0.
Since m divides 0 for all integers m (because 0 = 0(m)), the last statement is always true. Therefore a ≡ a (mod m) for all integers a and all choices of modulus m.
- TLKLv 49 years ago
a-a=0 \in mZ for any m. qed.