Results 1 to 4 of 4

Math Help - Cant solve these... Congruences !!

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    11

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,686
    Thanks
    617
    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}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Is there a fast way to solve this system of congruences on paper?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 19th 2010, 09:15 PM
  2. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 12:52 PM
  3. congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 5th 2009, 10:59 AM
  4. solve congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 17th 2009, 10:00 PM
  5. solve quadratic congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 12th 2008, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum