Math Is Fun Forum

wintersolstice

Real Member

Registered: 2009-06-06

Posts: 128

group theory problem

this problem has been driving me mental for such a long time and I just give up on it!

Basically if you have a number "n" and one of it's factors "r" (neither "r" nor" any of it's roots if any can have powers which are also factors of "n")

e.g. if you take 40, 2 as a factor 4 (it's square is a factor) or 4 (2 it's square root has 8 as a factor) so you could use 8 but not 2 or 4

if you take this function:

HCF(x,n) for x= 1,2,3,...n-1 this set (I think) forms a group "multiplication mod n"

I can prove the: inverse, associative and closure property but for the life of me I can't prve the indentity property,

I've tried finding a formula for it (it's not always the factor that is the identity element)
e.g. for 12 and it's factor 3 there are only two elements 3 and 9. 9 is the identity

I tried looking at it backwards given r consider it multiples (to account for the same problem as above don't multiply by another multiple of "r")

Has this result been proven (or disproven)? as if so what is the proof (disproof) is there a formula for the identity?

any help is most appreciated:D

---

Why did the chicken cross the Mobius Band?
To get to the other ...um...!!!

Avon

Member

Registered: 2007-06-28

Posts: 80

Re: group theory problem

Hi wintersolstice,

If I understand what you are doing correctly you are taking the set of all x=1,2,...,n-1 such that HCF(x,n)=r.
I think the condition you want on n and r is that HCF(r^2,n) = r.

To find the identity you need to solve the system of congruences

Since HCF(r^2, n) = r, we also have HCF(r, n/r) = 1 and so there is a unique solution modulo n.