Results 1 to 3 of 3

Thread: x^2\equiv 1 (mod p) and x^2\equiv 1 (mod q), where p and q are distinct primes

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10

    x^2\equiv 1 (mod p) and x^2\equiv 1 (mod q), where p and q are distinct primes

    $\displaystyle x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $\displaystyle x^2\equiv 1 \ \mbox{(mod pq)?}$

    $\displaystyle p|(x^2-1) \ \mbox{and} \ q|(x^2-1)$

    $\displaystyle pq|(x^2-1)^2\rightarrow (x^2-1)^2\equiv 0 \ \mbox{(mod pq)}$

    $\displaystyle \rightarrow (x^2-1)^2\equiv 0 \ \mbox{(mod pq)}\rightarrow 1^2\equiv 0 \ \mbox{(mod pq)}\rightarrow 1\not\equiv 0 \ \mbox{(mod pq)}$.

    Since this isn't true, then no??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    $\displaystyle x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $\displaystyle x^2\equiv 1 \ \mbox{(mod pq)?}$
    This is true.

    In general $\displaystyle a \equiv b\ (\text{mod}\ m)$ and $\displaystyle a \equiv b\ (\text{mod}\ n)$ implies $\displaystyle a \equiv b\ (\text{mod}\ \text{lcm}(m,n))$. See this MathWorld page, property #11.

    Quote Originally Posted by dwsmith View Post
    $\displaystyle (x^2-1)^2\equiv 0 \ \mbox{(mod pq)}\rightarrow 1^2\equiv 0 \ \mbox{(mod pq)}$
    I don't see how you made this step.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    $\displaystyle x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $\displaystyle x^2\equiv 1 \ \mbox{(mod pq)?}$
    This is correct and you have the right idea on how to prove it.

    See here for full a proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 15th 2011, 08:04 AM
  2. [SOLVED] Let p be odd. Then 2(p-3)!\equiv -1 (mod p)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jul 12th 2010, 03:42 PM
  3. [SOLVED] 2n^3+3n^2+n\equiv 0 (mod 6)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jul 8th 2010, 11:44 PM
  4. [SOLVED] if ab\equiv 0 (mod p), then a\equiv 0 (mod p) or b\equiv 0 (mod p).
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 7th 2010, 04:21 PM
  5. [SOLVED] if a^2 \equiv 1, then a \equiv \pm 1 (mod p)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jun 27th 2010, 03:43 PM

/mathhelpforum @mathhelpforum