# Help in some suggested questions about congruences, Fermat theorem (& maybe Wilson's)

• Jun 11th 2012, 02:49 PM
Rodrigomkt
Help in some suggested questions about congruences, Fermat theorem (& maybe Wilson's)
Hi people! That's my first time here in this forum, and I want to share with you some doubts.
My teacher of number's theorie suggested about 40 exercises about congruences, and I'm having trouble in some (5) of them.

There are the exercises:

EDIT: NOTATION: (a,b) is the greatest common divisor of a and b; N for Naturals, Z for Integers and P for primes; $\phi (a)$ is the Euler Totient of a.

1st) If $p, q \in P$ and $p \neq q$, so $p^{q-1} + q^{p-1} \equiv 1 \pmod{p.q}$.
-Observation: I think one problem is that I don't know how to create an useful relation in mod pq using relations on mod p and mod q. The only way that I know is the way that goes with the property: If $a \equiv b (mod n)$, so $a.c \equiv b.c \pmod{c.m}$ .

2nd) This second exercise is an generalization of the previous one (they are presented in this order).
If $a, b \in N$ and $(a,b) = 1$ , so $a^{\phi (b)} + b^{\phi (a)} \equiv 1 \pmod{a.b}$

3rd) The third problem is how to proof that $42|a^7 - a, \forall a \in Z.$

4th) Exercise: If $p, q \in P$, with $p \neq q$, are related as follows: $a^p \equiv a \pmod{q}$ and $a^q \equiv a \pmod{p}$, so $a^{pq} \equiv a \pmod{pq}$.
-Obs.: I think the observation posted in the first exercise will affect this one.

5th) If $a \in Z$ and $p,q \in P$, with $p \neq q$, so $p.q | a^{p+q} - a^{p+1} - a^{q+1} + a^2$.

I hope you can help me, any help (or try to) is very welcome!

Thanks,
Rodrigo.
• Jun 11th 2012, 10:17 PM
Sarasij
Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso

------------------------------------------------------------------------------------------------------------------
Solution to the third problem:

a7-1

= a(a6-1)

= a(a3+1)(a3-1)

= a(a+1)(a-1)(a2+a+1)(a2-a+1)

Clearly a(a+1) is divisible by 2 and a(a+1)(a-1) is divisible by 3.

Now the hard part is to show 7|(a7-1). When divided by 7 the possible remainders are 1,2,3,...,6.

If a≡1(mod 7) then a3≡1(mod 7).

If a≡2(mod 7) then a3≡8(mod 7)≡1(mod 7)

If a≡3(mod 7) then a3≡27(mod 7)≡-1(mod 7) i.e. a3+1≡0(mod 7)

If a≡4(mod 7) then a3≡64(mod 7)≡1(mod 7)

If a≡5(mod 7) then a3≡125(mod 7)≡-1(mod 7) i.e. a3+1≡0(mod 7)

If a≡6(mod 7) then a≡6(mod 7)≡-1(mod 7) i.e. a+1≡0(mod 7)

Therefore, the expression (a7-1) is always divisible by 3 primes 2 , 3 and 7. So its divisible by 2x3x7=42 for all integers a.
--------------------------------------------------------------------------------------------------------------------------------
Solution to the fourth problem:

p and q are primes , p and q are distinct and ap ≡ a (mod q) and aq ≡ a (mod p).

By Fermat's Little Theorem we know ap ≡ a (mod p) and aq ≡ a (mod q).

Therefore, ap ≡ a (mod q) => (ap)q ≡ aq (mod q) => apq ≡ aq (mod q) ≡ a (mod q)

Similarly aq ≡ a (mod p) => apq ≡ ap (mod q) ≡ a (mod q)

i.e ( apq - a) is divisible by both primes p and q where p and q are distinct. This implies that ( apq - a) is divisible by (pq) also.

So ( apq - a) ≡ 0 (mod pq) => apq ≡ a (mod pq).
--------------------------------------------------------------------------------------------------------------------------------

Solution to the 5th problem:

p and q are primes , p and q are distinct.

Now

ap+q - ap+1 - aq+1 + a2

= (ap - a )(aq - a)

= pK1 . qK2 for some integers K1 and K2[By Fermat's Little Theorem]

= (pq).K where K=K1.K2

Therefore pq | (ap+q - ap+1 - aq+1 + a2)
--------------------------------------------------------------------------------------------------------------------------------
• Jun 12th 2012, 04:54 AM
Rodrigomkt
Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso
Quote:

Originally Posted by Sarasij
[B]
--------------------------------------------------------------------------------------------------------------------------------
Solution to the fourth problem:

p and q are primes , p and q are distinct and ap ≡ a (mod q) and aq ≡ a (mod p).

By Fermat's Little Theorem we know ap ≡ a (mod p) and aq ≡ a (mod q).

Therefore, ap ≡ a (mod q) => (ap)q ≡ aq (mod q) => apq ≡ aq (mod q) ≡ a (mod q)

Similarly aq ≡ a (mod p) => apq ≡ ap (mod q) ≡ a (mod q)

i.e ( apq - a) is divisible by both primes p and q where p and q are distinct. This implies that ( apq - a) is divisible by (pq) also.

So ( apq - a) ≡ 0 (mod pq) => apq ≡ a (mod pq).

Thanks for all these exercise solutions Sarasij!
Specially for the 4th exercise solution, because of the property that you showed me (underlined). :)
With this property I solved the 1st and 2nd exercises easily.

Here's a more general version of the property: Be $a,b,k \in Z$, if $a|k$ and $b|k$ and $(a,b)=1$, so $a.b|k$ .

Thanks for all,
Rodrigo
• Jun 12th 2012, 06:30 AM
Sarasij
Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso
Quote:

Originally Posted by Rodrigomkt
Thanks for all these exercise solutions Sarasij!
Specially for the 4th exercise solution, because of the property that you showed me (underlined). :)
With this property I solved the 1st and 2nd exercises easily.

Here's a more general version of the property: Be $a,b,k \in Z$, if $a|k$ and $b|k$ and $(a,b)=1$, so $a.b|k$ .

Thanks for all,
Rodrigo

You are welcome...if you liked my solutions then I request you to give thanks to my user account by clicking the "Thanks" shown at the end of my replies.(Of course this is not mandatory,but in case if you want to...) (Cool)