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!

3 Answers

Relevance
  • Favorite 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!

  • 9 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.

  • TLK
    Lv 4
    9 years ago

    a-a=0 \in mZ for any m. qed.

Still have questions? Get your answers by asking now.