Results 1 to 3 of 3

Math Help - Questions about Number Theory

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    3

    Questions about Number Theory

    need help on the following two questions

    1.


    2.



    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by toxiccan View Post
    1.
    We must have n>1 since 1 is a perfect square. Thus n can be written as a product of distinct primes: n=p_1^{m_1}p_2^{m_2}\ldots p_r^{m_r} (m_i\ge1).

    Now if all the m_iís were even, n would be a perfect square. Since it isnít, at least one of the m_iís must be odd. Hence, we can write n=p^mk where m is odd and p does not divide k.

    Suppose \sqrt{n} is rational: \sqrt{n}=\frac{a}{b}, where a,b\in\mathbb{Z}, b\ne0 and \gcd(a,b)=1.

    Then a^2=nb^2=p^mkb^2

    \therefore p\mid a^2 \Rightarrow p\mid a as p is prime \Rightarrow p\nmid b as \gcd(a,b)=1.

    Hence the factor of p occurs an odd number of times in p^mkb^2 = a^2. This is a contradiction because a^2 is a perfect square and so each prime factor of a^2 has to occur an even number of times.

    Thus \sqrt{n} must be irrational.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by toxiccan View Post
    2.
    It suffices to prove that x^2+y^2+1\equiv 0(\bmod p) has a solution with 0\leq x,y\leq \tfrac{p-1}{2}.
    Let A = \{ 1 + 0^2,1+1^2,...,1+\left( \tfrac{p-1}{2} \right)^2\}.
    Let B = \{ -0^2,-1^2,...,-\left( \tfrac{p-1}{2} \right)^2\}.
    If x,y \in A then x=1+x_0^2 and y=1+y_0^2. If x\equiv y(\bmod p) then it means y_0^2 \equiv x_0^2(\bmod p) so x_0\equiv \pm y_0 (\bmod p). The negative sign is impossible so x_0=y_0\implies x=y. Thus distinct elements in that set are not congruent to eachother. Thus, |A| = 1+\tfrac{p-1}{2}. Using a similar argument we can show |B| = 1+\tfrac{p-1}{2}. This means altogether A and B has 2(1+\tfrac{p-1}{2}) = p+1 elements. Thus, by pigeonhole principle there is a\in A and b\in B such that a\equiv b(\bmod p) because the set of remainders mod p is size p. Thus, 1+x^2 \equiv - y^2(\bmod p).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  3. number theory
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 3rd 2008, 04:31 PM
  4. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 5th 2008, 02:01 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum