Modular algebra problems

I got some problem with those demonstrations and I don't know where I'm wrong, let me show you my steps:

1: first of all

$6 | 2n(n^2 +2)$

That is, I must demonstrate that $6$ divides $2n(n^2 +2)$ , so I just simplify this stuff dividing by two:

$3 | n(n^2+2)$

to solve this I thought to model this with a simple modular algebra problem of the type:

$n(n^2+2)≡0 ($mod $3)$

That is, I must try to satisfy this system of modular equations:

$n≡0($mod $3)$

$n^2≡-2($mod $3)$

but the amount of numbers that are smaller than 3 and co-prime with it are 2, and $gcd(2,2)=2$ meaning that we can't find the inverse of the application $x → x^2$.

2: Let $A:=Z/50Z$ and let $B:= (Z/50Z)*$ be the subset of A made of its invertible classes (mod 50). Calculate the cardinality of the following sets:

$X:=C∈2^A|B⊂C$;

$Y:=f∈A^A|f(B) =B$;

$Z:=f∈Y|$ f is injective.

with this I don't even know where to start :(

• for first problem you may use the fact that $n^2 \equiv 1 \mod 3$ when $3 \not | n$ – ganeshie8 Aug 22 '14 at 10:52

Hint:

1. Use induction

2. $x\in B$ iff $(x,50)=1$ (coprime). To count the number, you need the Euler Phi function.

$X$ is the collection of all subsets of $A$ that contains $B$. To define one such subset, you need to assign $0$ or $1$ to each element outside $B$ ($1$ means the subset has it and $0$ means it does not), and therefore $|X|=2^{|A|-|B|}$.

$Y$ is the collection of all functions from $A$ to $A$ that fixes $B$. Basically, you first need to assign value $f(x)$ for each element $x\not\in B$, and the number of choices is $|A|^{|A|-|B|}$. Next, $f|B$ is surjective and therefore also bijective, and therefore $\{f|B: f(B)=B\}$ is the permutation group of $B$, with cardinality $|B|!$. Overall, you have $|Y|=|A|^{|A|-|B|}\cdot |B|!$.

$Z$ is injective functions from $A$ to $A$. You need to ensure $f|B$ and $f|(A-B)$ are both injective, and therefore both bijective. Therefore, $|Z|=|B|!\cdot (|A|-|B|)!$.

• Thank you Troy! what I don't understand is.. |B| = 20 right? In the sense that x can assume just 20 different values to make (x,50)=1 – user2993157 Aug 22 '14 at 11:54
• @user2993157 true, since $50=2\cdot 5^2$ and $\phi(50)=2^0(2-1)5^1(5-1)=20$. – Troy Woo Aug 22 '14 at 12:02
• @user2993157 Don't forget to approve if you think its correct ;-). – Troy Woo Aug 22 '14 at 12:36
• and the cardinality of A is 50? sorry but I just can't get the intuition behind what Z/nZ really means and so its cardinality... :/ – user2993157 Aug 22 '14 at 13:39
• @user2993157 ...... two numbers are congruent if they differ by a number of $n$'s,e.g. when $n=50$, $1=51=101=\dots$. Therefore, there are only 50 distinct elements $0,1,\dots,49$ in comparison to infinite number of numbers in $\mathbb Z$ – Troy Woo Aug 22 '14 at 14:33

You may try below for first problem :

$n(n^2+2) = n(n^2-1+3) = n(n^2-1) + 3n = (n-1)n(n+1) + 3n$

• ahah great trick! it's a lot intuitive, every three successive numbers there's a multiple of 3, thank you very much sir! – user2993157 Aug 23 '14 at 14:16