mod arith & prime numbers: If x = a (mod n), prove that....

[JennyJ]

first problem:

If x=a (mod n), prove that either x=a (mod 2n) or x=a+n (mod 2n).

dont really know where to begin.

second problem:

If p and q are distinct primes, prove that
p[sup:3hgk2h56]q-1[/sup:3hgk2h56] + q[sup:3hgk2h56]p-1[/sup:3hgk2h56] = 1 (mod pq)

 

[daon]

Re: mod arith & prime numbers

For 1: Assume x = a (mod n) and x does not equal a (mod 2n). Then your goal is to show x=a+n (mod 2n)

So... n|(x-a), but 2n\(\displaystyle \not |\) (x-a)... so (x-a)/n is odd...

n|(x-a) means x = a+nL for some L, and L is odd since L = (x-a)/n.

Write L=2K+1 for some K.

So x = a+n(2K +1) = (a+n) + 2n(K). Thus x = a+n (mod 2n).

...

For 2) Use Fermat's little theorem:

\(\displaystyle p^{q-1}=1\,\, (mod \,\, q)\)
\(\displaystyle q^{p-1}=1 \,\, (mod \,\, p)\)

 

[JennyJ]

Re: mod arith & prime numbers

ok for #2 I understand using Fermat's Little Theorem but what is the rule since we are modding out by pq. can you just multiply together ? sorry if this a dumb question but I find my textbook really confusing.