# Thread:

1. ## 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!

2. 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} = <br /> (a^{n-1}-a^{n-2}b+...+b^{n-1}<br />$

-Andy

3. Hello, guidol92!

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}<br /> 7^1 & \equiv & 7 & \text{ (mod 9)} \\ <br /> 7^2 & \equiv & 4 & \text{ (mod 9)} \\<br /> 7^3 & \equiv & 1 & \text{ (mod 9)} \\<br /> 7^4 & \equiv & 7 & \text{ (mod 9)} \\<br /> \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}$

4. 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).
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 13, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8084111213684082, "perplexity_flag": "middle"}