Thread: 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!

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 factors into

.

So,

-Andy

Hello, guidol92!

c) Find the remainder when is divided by 9.

We are working in modulo 9.


We find that: .

Hence: .


Then we see that:

. .


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


Since

. . we have: .

. . . . . . . . . . . . .

for(b):
there is no natural number satisfying the condition.
since 5 divides 1955, but (mod 5) has no solution, we obtain that there is no natural number such that 1955 divides .
for(d)(1): applying the fermat's little theorem, we get pq divides both .
for(2), that is impossible according to (1).