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.