• Support PF! Buy your school textbooks, materials and every day products Here!

Number theory

  • Thread starter oddiseas
  • Start date
  • #1
73
0

Homework Statement


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.


Homework 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.


The Attempt at a Solution

 

Answers and Replies

  • #2
352
0
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.
 
  • #3
73
0
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
73
0
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.
 

Related Threads on Number theory

  • Last Post
Replies
4
Views
905
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
717
  • Last Post
Replies
2
Views
759
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
962
  • Last Post
Replies
2
Views
912
  • Last Post
Replies
4
Views
1K
Top