0
$\begingroup$

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 :(

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

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|)!$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user2993157 Aug 22 '14 at 11:54
  • $\begingroup$ @user2993157 true, since $50=2\cdot 5^2$ and $\phi(50)=2^0(2-1)5^1(5-1)=20$. $\endgroup$ – Troy Woo Aug 22 '14 at 12:02
  • $\begingroup$ @user2993157 Don't forget to approve if you think its correct ;-). $\endgroup$ – Troy Woo Aug 22 '14 at 12:36
  • $\begingroup$ 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... :/ $\endgroup$ – user2993157 Aug 22 '14 at 13:39
  • $\begingroup$ @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$ $\endgroup$ – Troy Woo Aug 22 '14 at 14:33
1
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.