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

Printable View

June 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.
June 11th 2012, 10:17 PM
Sarasij

Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso

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

a⁷-1

= a(a⁶-1)

= a(a³+1)(a³-1)

= a(a+1)(a-1)(a²+a+1)(a²-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|(a⁷-1). When divided by 7 the possible remainders are 1,2,3,...,6.

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

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

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

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

If a≡5(mod 7) then a³≡125(mod 7)≡-1(mod 7) i.e. a³+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 (a⁷-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 a^p≡ a (mod q) and a^q≡ a (mod p).

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

Therefore, a^p≡ a (mod q) => (a^p)^q≡ a^q (mod q) => a^pq≡ a^q (mod q) ≡ a (mod q)

Similarly a^q≡ a (mod p) => a^pq≡ a^p (mod q) ≡ a (mod q)

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

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

Solution to the 5th problem:

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

Now

a^p+q - a^p+1 - a^q+1 + a²

= (a^p - a )(a^q - a)

= pK₁ . qK₂ for some integers K₁ and K₂[By Fermat's Little Theorem]

= (pq).K where K=K₁.K₂Therefore pq | (a^p+q - a^p+1 - a^q+1 + a²)
--------------------------------------------------------------------------------------------------------------------------------
June 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 a^p≡ a (mod q) and a^q≡ a (mod p).

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

Therefore, a^p≡ a (mod q) => (a^p)^q≡ a^q (mod q) => a^pq≡ a^q (mod q) ≡ a (mod q)

Similarly a^q≡ a (mod p) => a^pq≡ a^p (mod q) ≡ a (mod q)

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

So ( a^pq- a) ≡ 0 (mod pq) => a^pq ≡ 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
June 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)