1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory

  1. Mar 8, 2010 #1
    1. The problem statement, all variables and given/known data
    This question i am having trouble with.
    Let n be an odd positive integer. Prove there is a one-to-one correspondence
    between the factorisation of n into the form n = ab where a >=b >= 1, and
    representations of the form s ^2-t^2where s, t ∈ Z satisfy s > t >=0.

    2. Relevant equations
    I have set n=ab=s²-t²=(s+t)(s-t)
    and solved for s and t, i have then showed by use of congruences that the sum and differenc of two odd integers is even, and thus s and t are even,but i am still having trouble fully understanding how exactly and why there is a one to one corespondance. If anyone understands this concept properly i would like some help as i am not fully grasping it.

    3. The attempt at a solution
  2. jcsd
  3. Mar 8, 2010 #2
    There is nothing you're missing here; you have identified all the important ideas.

    It may help you to formalize things a little bit more. Try to exhibit an explicit one-to-one correspondence between the two sets [tex]A = \{ (a, b) \in \mathbb{Z}\times\mathbb{Z} \mid a \geq b \geq 1 \textrm{ and } ab = n \}[/tex] and [tex]B = \{ (s, t) \in \mathbb{Z}\times\mathbb{Z} \mid s \geq t \geq 0 \textrm{ and } s^2 - t^2 = n \}[/tex]. This means you should give a bijective (one-to-one and onto) function [tex]f: A \to B[/tex]. You can prove that [tex]f[/tex] is bijective by proving directly that it is both injective (one-to-one) and surjective (onto); or you can accomplish the same thing by exhibiting an inverse [tex]g: B \to A[/tex], i.e., a function such that [tex]g\circ f = \mathrm{id}_A[/tex] and [tex]f\circ g = \mathrm{id}_B[/tex].

    You have already figured out the computation that defines [tex]f[/tex] and [tex]g[/tex]; you just need to carry out the formal proof.
  4. Mar 8, 2010 #3
    Thanks, thats a good response.

    Thats the approach i took the first time trying to solve this problem, but then rubbed it out because i thought it was wrong. What i did was show that for all odd integers the mapping f=s^2-t^2 takes a point from a set A, where A consists of only odd integers and maps it to an element of a set B, where B contains only even integers, since the difference of two odd integers is always even. But then i just stated that since every prime factorisation is unique so too is the difference and thus the mapping is unique for each element in A and thus a one to one mapping, but i am still not sure this is formal enough. How can i formalise this argument properly?
    (I have just started groups, rings etc so i sort of get the significant of inverse elements as you stated, but not properly yet) How can i show that an inverse mapping exists and under what "operation" do i define the identity element, and how exactly is this "significant" in showing a one to one correspondance( ie injective and surjective)
  5. Mar 9, 2010 #4
    After looking at this for the last few hours now im getting confused.If n is odd, then a and b are odd and thus s and t will be even and so too will the mapping. Then the set B will contain all even integers. In addition an even integer can be represented as a difference of two odd squares in multiple ways, thus i have shown that the mapping is surjective but definitely not injective which is the opposite of what the question asks us to show.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Number theory
  1. Number Theory (Replies: 2)

  2. Number theory ! (Replies: 4)

  3. Number Theory (Replies: 2)

  4. Number Theory (Replies: 11)

  5. Number theory (Replies: 5)