Results 1 to 3 of 3

Thread: 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 $\displaystyle n>1$ since 1 is a perfect square. Thus n can be written as a product of distinct primes: $\displaystyle n=p_1^{m_1}p_2^{m_2}\ldots p_r^{m_r}$ $\displaystyle (m_i\ge1)$.

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

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

    Then $\displaystyle a^2=nb^2=p^mkb^2$

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

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

    Thus $\displaystyle \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
    10
    Quote Originally Posted by toxiccan View Post
    2.
    It suffices to prove that $\displaystyle x^2+y^2+1\equiv 0(\bmod p)$ has a solution with $\displaystyle 0\leq x,y\leq \tfrac{p-1}{2}$.
    Let $\displaystyle A = \{ 1 + 0^2,1+1^2,...,1+\left( \tfrac{p-1}{2} \right)^2\}$.
    Let $\displaystyle B = \{ -0^2,-1^2,...,-\left( \tfrac{p-1}{2} \right)^2\}$.
    If $\displaystyle x,y \in A$ then $\displaystyle x=1+x_0^2$ and $\displaystyle y=1+y_0^2$. If $\displaystyle x\equiv y(\bmod p)$ then it means $\displaystyle y_0^2 \equiv x_0^2(\bmod p)$ so $\displaystyle x_0\equiv \pm y_0 (\bmod p)$. The negative sign is impossible so $\displaystyle x_0=y_0\implies x=y$. Thus distinct elements in that set are not congruent to eachother. Thus, $\displaystyle |A| = 1+\tfrac{p-1}{2}$. Using a similar argument we can show $\displaystyle |B| = 1+\tfrac{p-1}{2}$. This means altogether $\displaystyle A$ and $\displaystyle B$ has $\displaystyle 2(1+\tfrac{p-1}{2}) = p+1$ elements. Thus, by pigeonhole principle there is $\displaystyle a\in A$ and $\displaystyle b\in B$ such that $\displaystyle a\equiv b(\bmod p)$ because the set of remainders mod $\displaystyle p$ is size $\displaystyle p$. Thus, $\displaystyle 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: Jul 8th 2011, 06:09 PM
  2. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  3. number theory
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 3rd 2008, 04:31 PM
  4. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 5th 2008, 02:01 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum