# Discrete math proof needed

**Question**

It is asking for the proof for lemma X. According to the discussion in class we know that when you have something like a mod j. that translate into:

a = jq + r where 0 <= r < j

also r has to be the smallest number possible. I just don’t know how to go about it. The lema in question is showned below.

Lemma X : Given j > 1 and k > 1. If a mod jk = 1 then

a mod j = 1 and a mod k = 1.

how can I prove that?

**Answer**

Lemma X : Given j > 1 and k > 1. If a mod jk = 1 then

a mod j = 1 and a mod k = 1.

Firstly,

a mod jk = 1 means,

a = 1 + jkh for some integer h.

Now call kh = M and see that,

a = 1 + jM. So, a mod j = 1. because our ‘r’ here is ‘1’ and satisfies, 0 <= 1 < j. And using the “definition” of “mod” that you gave.

Similarly call jh = N and see that,

a = 1 + kN. So a mod k = 1. because our ‘r’ here is ‘1’ and satisfies, 0 <= 1 < j. And using the “definition” of “mod” that you gave.

QED.