Proof in reduced residues please help

  • Thread starter frowdow
  • Start date
  • #1
4
0

Main Question or Discussion Point

I am teaching myself number theory using George Andrews book. i am stuck in the following problem:

To prove that as x cycles thru' the reduced residue set modulo m & y cycles thru' reduced residue set modulo n, nx + my cycles thru' reduced residue set modulo mn.

I am able to prove that:
a) nx1 + my1 [STRIKE]=[/STRIKE] nx2 + my2 and
b) nx + my is relatively prime to mn

But how do i prove that nx + my cycles thru' every one of the reduced residue set modulo mn without first proving that [tex]\phi[/tex][tex]\left(xy\right)\neq[/tex][tex]\phi\left(x\right)\phi\left(y\right)[/tex]
 

Answers and Replies

  • #2
12,941
9,592
This description is a bit weird. Look up the chinese remainder theorem and the Euclidean algorithm. I guess that ##n,m## are coprime.
 

Related Threads on Proof in reduced residues please help

Replies
8
Views
6K
  • Last Post
Replies
16
Views
4K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
4
Views
3K
Top