Discrete math proof needed?

Question

I need this for a test tomorrow. 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 1

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.

Hope this helped.

:)

Answer 2

Are you familiar with modular arithmetic? if so, proving this may well be a breeze. The modular arithmetic way: we would desire to instruct a^3 - a is congruent to 0 mod(3) for a=0, 0-0 is congruent to 0 mod(3) for a=a million, a million-a million=0 is congruent to 0 mod(3) for a=2, 8-2=6 is congruent to 0 mod(3) for this reason, a^3 -a is congruent to 0 mod(3) <===> 3 divides a^3 -a . And we are executed :) yet while no longer, we are able to do it the good way: 3 divides a^3 - a skill 3k=a^3 -a, the place ok is an integer [that's what we would desire to instruct] So we've 2 situations: --Case a million: a is even: a=3s, the place s is a good integer then, a^3 -a = (3s)^3 - 3s =27s^3-3s =3[9s^3-s] via fact that 9s^3 -s is an integer, we've the type 3k --Case 2: a is extraordinary: a=3s+a million, the place s is a good integer then a^3-a = (3s+a million)^3 - (3s+a million) =(9s^2+6s+a million)^2(3s+a million) - (3s+a million) =27s^3+9s^2+18s^2+6s+3s+a million - (3s+a million) integrate like words and we get: 27s^3+27s^2+6s =3[9s^3+9s^2+2s] via fact that [9s^3+9s^2+2s] is an integer, we've the type 3k And we are executed :)

Answer 3

If a mod jk ≡ 1 then there is some integer q such that
a = q * jk + 1
Therefore,
a = (qk)j + 1, or a ≡ 1 (mod j)
since there is some integer m such that a = mj + 1 (m = qk)
and
a = (qj)k + 1, or a ≡ 1 (mod k)
since there is some integer n such that a = nk + 1 (n = qj)