# Number theory

1. Mar 8, 2010

### oddiseas

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. Mar 8, 2010

### ystael

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 $$A = \{ (a, b) \in \mathbb{Z}\times\mathbb{Z} \mid a \geq b \geq 1 \textrm{ and } ab = n \}$$ and $$B = \{ (s, t) \in \mathbb{Z}\times\mathbb{Z} \mid s \geq t \geq 0 \textrm{ and } s^2 - t^2 = n \}$$. This means you should give a bijective (one-to-one and onto) function $$f: A \to B$$. You can prove that $$f$$ 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 $$g: B \to A$$, i.e., a function such that $$g\circ f = \mathrm{id}_A$$ and $$f\circ g = \mathrm{id}_B$$.

You have already figured out the computation that defines $$f$$ and $$g$$; you just need to carry out the formal proof.

3. Mar 8, 2010

### oddiseas

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)

4. Mar 9, 2010

### oddiseas

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.