- I was looking at

http://www.primepuzzles.net/problems/prob_037.htm

and in the proof of the formula mr Fengsui claims that

"...the class of residues Tn mod mn is equivalent to the class of

residues Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1],"

could anyone explain to me in simple terms why this is?

any help will be greatly appreciated. have a good day. - 'Suppose that: the Tn is a complete set of residues prime to mn, the least

number more than 1 in this set U(Tn) is the n-th prime pn. The number of

elements of the set Tn is | Tn |=(p1-1)*(P2-1)*...*(p[n-1]-1). If p>p[n-1]

is a prime, then p belongs the class of residues Tn mod mn.'

I don't get this. mn is defined as "Let mn=p0*p1*...p[n-1]", therefore

m2=2.3=6 and m3=2.3.5=30

However, the number of residues prime to 30 is

|{2,3,5,7,11,13,17,19,23,29}|=10, and not the 8 predicted by Liu. I suppose

the p>3 property comes into play...

'If p>p[n-1] is a prime, then p belongs the class of residues Tn mod mn.'

Suppose p is a prime and p doesn't belong to tmod30, this is impossible.

Induction carries on from here.

I think what '"...the class of residues Tn mod mn is equivalent to the class

of

residues Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1],"'

means is that we are looking at either (pn,mn)=1 OR (tn+pn,mn)=1.

HTH

Jon Perry

perry@...

http://www.users.globalnet.co.uk/~perry/maths/

http://www.users.globalnet.co.uk/~perry/DIVMenu/

BrainBench MVP for HTML and JavaScript

http://www.brainbench.com

-----Original Message-----

From: velozant <velozant@...> [mailto:velozant@...]

Sent: 28 February 2003 22:15

To: primenumbers@yahoogroups.com

Subject: [PrimeNumbers] reduced residue systems question please help

I was looking at

http://www.primepuzzles.net/problems/prob_037.htm

and in the proof of the formula mr Fengsui claims that

"...the class of residues Tn mod mn is equivalent to the class of

residues Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1],"

could anyone explain to me in simple terms why this is?

any help will be greatly appreciated. have a good day.

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

The Prime Pages : http://www.primepages.org/

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ - --- Jon Perry <perry@...> wrote:
> 'Suppose that: the Tn is a complete set of residues prime to mn, the least

Woh! Steady on, Jon. You're _way_ off base here.

> number more than 1 in this set U(Tn) is the n-th prime pn. The number of

> elements of the set Tn is | Tn |=(p1-1)*(P2-1)*...*(p[n-1]-1). If p>p[n-1]

> is a prime, then p belongs the class of residues Tn mod mn.'

>

> I don't get this. mn is defined as "Let mn=p0*p1*...p[n-1]", therefore

> m2=2.3=6 and m3=2.3.5=30

>

> However, the number of residues prime to 30 is

> |{2,3,5,7,11,13,17,19,23,29}|=10, and not the 8 predicted by Liu. I suppose

> the p>3 property comes into play...

2 is not coprime to 30. gcd(2,30)=2

3 is not coprime to 30. gcd(3,30)=3

5 is not coprime to 30. gcd(5,30)=5

1 is coprime to 30. gcd(1,30)=1

|{1,7,11,13,17,19,23,29}| = 8 as correctly stated by Liu.

And Liu was not "predicting", this isn't reading chicken entrails, it's a

simple mathematical fact.

Phil

=====

"Only an admission that he does possess weapons of mass destruction

would do, sources said: 'The rest is just gesture politics." -- Hoon

"Are you still bombing your wife?" -- Winjer

__________________________________________________

Do you Yahoo!?

Yahoo! Tax Center - forms, calculators, tips, more

http://taxes.yahoo.com/ - 'Woh! Steady on, Jon. You're _way_ off base here.

2 is not coprime to 30. gcd(2,30)=2

3 is not coprime to 30. gcd(3,30)=3

5 is not coprime to 30. gcd(5,30)=5

1 is coprime to 30. gcd(1,30)=1

|{1,7,11,13,17,19,23,29}| = 8 as correctly stated by Liu.'

Correct. As the whole page in question

(http://www.primepuzzles.net/problems/prob_037.htm) is completely littered

with typos and misleading nomenclature, I don't feel completely aggrieved at

having made such a simple error.

As to what 'Tn mod mn is equivalent to the class of residues

Tn+<0,1,2,...,pn=1>*<mn> mod m[n+1]'

means, it should read:

T_n mod m_n is equivalent to the class of residues

Tn+(<0,1,2,...,pn-1>*<mn>) mod m_(n+1)

which comes clear if you look at the examples, except for m_n is incorrectly

defined.

Jon Perry

perry@...

http://www.users.globalnet.co.uk/~perry/maths/

http://www.users.globalnet.co.uk/~perry/DIVMenu/

BrainBench MVP for HTML and JavaScript

http://www.brainbench.com - Thanks a lot for your responses. What I am confused about is that I

don't understand how adding <0,1,2,...,pn-1>*<mn> to Tn makes it

equivalent mod m[n+1]. What I would like is a theorem like the one

that one can uset to prove that if (k,S)=1 and S is a reduced

residue system then so is k*S. I think it should be obvious since

most people accept it and I see from examples that it is true, but I

just want to know what theorem he is using to imply this equivalence

or if it follows directly from the definition of Tn. Any help will

be greatly appreciated.