# 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!

Relevance
• 9 years ago

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.