22.2k views
0 votes
Prove that u(n) is a group under the operation of multiplication modulo n.

User Slikts
by
4.7k points

2 Answers

3 votes

Answer:

The answer is the proof so it is long.

The question doesn't define u(n), but it's not hard to guess.


Group G with operation ∘

For all a and b and c in G:

1) identity: e ∈ G, e∘a = a∘e = a,

2) inverse: a' ∈ G, a∘a' = a'∘a = e,

3) closed: a∘b ∈ G,

4) associative: (a∘b)∘c = a∘(b∘c),

5) (optional) commutative: a∘b = b∘a.


Define group u(n) for n prime is the set of integers 0 < i < n with operation multiplication modulo n.


If n isn't prime, we exclude from the group all integers which share factors with n.


Identity: e = 1. Clearly 1∘a = a∘1 = a. (a is already < n).


Closed: u(n) is closed for n prime. We must show that for all a, b ∈ u(n), the integer product ab is not divisible by n, so that ab ≢ 0 (mod n). Since n is prime, ab ≠ n. Since a < n, b < n, no factors of ab can equal prime n. (If n isn't prime, we already excluded from u(n) all integers sharing factors with n).


Inverse: for all a ∈ u(n), there is a' ∈ u(n) with a∘a' = 1. To find a', we apply Euclid's algorithm and write 1 as a linear combination of n and a. The coefficient of a is a' < n.


Associative and Commutative:

(a∘b)∘c = a∘(b∘c) because (ab)c = a(bc)

a∘b = b∘a because ab = ba.


User Andrew Briggs
by
5.7k points
3 votes

Answer:

The answer is the proof so it is long.

The question doesn't define u(n), but it's not hard to guess.


Group G with operation ∘

For all a and b and c in G:

1) identity: e ∈ G, e∘a = a∘e = a,

2) inverse: a' ∈ G, a∘a' = a'∘a = e,

3) closed: a∘b ∈ G,

4) associative: (a∘b)∘c = a∘(b∘c),

5) (optional) commutative: a∘b = b∘a.


Define group u(n) for n prime is the set of integers 0 < i < n with operation multiplication modulo n.


If n isn't prime, we exclude from the group all integers which share factors with n.


Identity: e = 1. Clearly 1∘a = a∘1 = a. (a is already < n).


Closed: u(n) is closed for n prime. We must show that for all a, b ∈ u(n), the integer product ab is not divisible by n, so that ab ≢ 0 (mod n). Since n is prime, ab ≠ n. Since a < n, b < n, no factors of ab can equal prime n. (If n isn't prime, we already excluded from u(n) all integers sharing factors with n).


Inverse: for all a ∈ u(n), there is a' ∈ u(n) with a∘a' = 1. To find a', we apply Euclid's algorithm and write 1 as a linear combination of n and a. The coefficient of a is a' < n.


Associative and Commutative:

(a∘b)∘c = a∘(b∘c) because (ab)c = a(bc)

a∘b = b∘a because ab = ba.


User Spenser
by
5.7k points