# Cant solve these... Congruences !!

• January 3rd 2010, 06:16 PM
guidol92
Cant solve these... Congruences !!
Hello, i want to share some problems that i found in the internet, but i cannot verify the solutions and others i dont know how to solve them,

here:

a) If N is a odd natural number, show that a+b divides (a^n)+(b^n)

b) There exist a natural number N such that 1955 divides n^2+n+1 ?

c) Find the remainder when 4444^4444 is divided by 9.

d) p & q are different primes, show that
1) p^q + q^p i is congruent to p+q (mod pq)
2) (p^q + q^p)/(pq) is even, if p & q is not equal to 2.

a step by step solution will be great, please.. thank you!
• January 3rd 2010, 09:58 PM
abender
Quote:

a) If N is a odd natural number, show that a+b divides (a^n)+(b^n)
If n is an odd natural number, then $a^n +b^n$ factors into

$(a+b)(a^{n-1}-a^{n-2}b+...+b^{n-1})$ .

So,

$\frac{a^n+b^n}{a+b} =
(a^{n-1}-a^{n-2}b+...+b^{n-1}
$

-Andy
• January 4th 2010, 06:17 AM
Soroban
Hello, guidol92!

Quote:

c) Find the remainder when $4444^{4444}$ is divided by 9.
We are working in modulo 9.

We find that: . $4444\:\equiv\:7\text{ (mod 9)}$

Hence: . $4444^{4444}\:\equiv\:7^{4444}\text{ (mod 9)}$

Then we see that:

. . $\begin{array}{cccc}
7^1 & \equiv & 7 & \text{ (mod 9)} \\
7^2 & \equiv & 4 & \text{ (mod 9)} \\
7^3 & \equiv & 1 & \text{ (mod 9)} \\
7^4 & \equiv & 7 & \text{ (mod 9)} \\
\vdots &&\vdots \end{array}$

The powers-of-7 have a three-step cycle.

Since $4444 \:=\:3(1481) + 1$

. . we have: . $7^{4444} \:\equiv\:7^{3(1481) + 1} \:\equiv\:7^{3(1481)}\cdot7^1$

. . . . . . . . . . . . . $\equiv\:\left(7^3\right)^{1481}\cdot7 \;=\; 1^{1481}\cdot7 \;\equiv\;\boxed{7}$

• January 4th 2010, 07:57 AM
Shanks
for(b):
there is no natural number satisfying the condition.
since 5 divides 1955, but $n^2+n+1\equiv 0$ (mod 5) has no solution, we obtain that there is no natural number such that 1955 divides $n^2+n+1$.
for(d)(1): applying the fermat's little theorem, we get pq divides both $p^q-p, q^p-q$.
for(2), that is impossible according to (1).