Results 1 to 4 of 4

Thread: 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
    339
    Thanks
    46
    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 $\displaystyle a^n +b^n $ factors into

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

    So,

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

    -Andy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    849
    Hello, guidol92!

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


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

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


    Then we see that:

    . . $\displaystyle \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 $\displaystyle 4444 \:=\:3(1481) + 1$

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

    . . . . . . . . . . . . .$\displaystyle \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 $\displaystyle n^2+n+1\equiv 0$ (mod 5) has no solution, we obtain that there is no natural number such that 1955 divides $\displaystyle n^2+n+1$.
    for(d)(1): applying the fermat's little theorem, we get pq divides both $\displaystyle 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: Oct 19th 2010, 09:15 PM
  2. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Mar 11th 2010, 12:52 PM
  3. congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 5th 2009, 10:59 AM
  4. solve congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 17th 2009, 10:00 PM
  5. solve quadratic congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 12th 2008, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum