Results 1 to 3 of 3

Math Help - Help With Congruence Problems

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    10

    Help With Congruence Problems

    Hello, everyone! Just wanted some ideas regarding the following problems.

    1) Let a and b be integers and p be a prime number. Prove the following:
    a) a^2 = b^2 mod p implies that a = ħb mod p.
    b) a^2 = a mod p implies that a = 0 mod p or a = 1 mod p.

    2) Let p be prime and (a,p) = (b,p) = 1. Prove the following:
    a) a^p = b^p mod p implies that a = b mod p.
    b) a^p = b^p mod p implies that a^p = b^p mod p^2.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by carabidus View Post
    Hello, everyone! Just wanted some ideas regarding the following problems.

    1) Let a and b be integers and p be a prime number. Prove the following:
    a) a^2 = b^2 mod p implies that a = ħb mod p.


    \color{red}a^2 \equiv b^2\,(mod\,p)\Longleftrightarrow (a-b)(a+b)=a^2-b^2\equiv 0\,(mod\,p)\Longleftrightarrow p\mid(a-b)(a+b)
    \color{red}\mbox{Since p is a prime then....}


    b) a^2 = a mod p implies that a = 0 mod p or a = 1 mod p.


    \color{red}a^2=a\Longleftrightarrow a(a-1)=0


    2) Let p be prime and (a,p) = (b,p) = 1. Prove the following:
    a) a^p = b^p mod p implies that a = b mod p.


    \color{red}\mbox{Read about Fermat's Little Theorem (FLT):}a^p\equiv a (mod\,p)

    b) a^p = b^p mod p implies that a^p = b^p mod p^2.


    \color{red}\mbox{Apply FLT to get}\,\,a \equiv b\,(mod\,p)\Longrightarrow a-b=kp\,,\,\,with\,\,k\in \mathbb{Z}\,...etc.

    \color{red}Tonio

    Thanks!
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    10
    Hey, thanks Tonio! Here are more congruent problems I've been pondering:

    1) Show that for every positive integer m there are infinitely many Fibonacci numbers F_n such that m divides F_n .

    2) Let p be an odd prime and k be a positive integer. Show that x^2=1 mod p^k has exactly 2 two noncongruent solutions.

    3) Develop a test for divisibility based on the fact that 10^3=1 mod 37. Use this to check 11092785 for divisibility by 37.

    4) Let p be prime and let {a_1, a_2, ... , a_p} and {b_1, b_2, ... , b_p} be complete sets of residues mod p. Show that {a_1*b_1, a_2*b_2 , ... , a_p*b_p} is NOT a complete set of residues mod p.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. some of congruence problems
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 16th 2011, 04:28 AM
  2. Congruence Problems
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 18th 2010, 10:30 PM
  3. Congruence problems
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 26th 2010, 06:30 PM
  4. Help with understanding congruence problems
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 26th 2009, 02:56 AM
  5. Congruence problems
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 11th 2009, 11:15 AM

Search Tags


/mathhelpforum @mathhelpforum