# Thread: number theory and abstract algebra

1. ## number theory and abstract algebra

Just hoping for some help with my practice exam. Any help on any of the questions would be greatly appreciated as my lecturer is absolutely shocking. Cheers.

(2)b

Let n ∈ N and let p be a prime. Show that if p | n then φ(np) = pφ(n).
Hint: consider the prime factorisation of n.

(17)
Show that the inverse of 5 modulo 101 is 5^99.
Use repeated squaring to simplify 5^99 (mod101)
Hence solve the equation 5x = 31(mod101)

(31)
Let P(R) be the set of all subsets of R; that is, P(R) = {X | X ⊆ R}. Let F be the set of all functions R → R. Define R : F → P(R) by R(f ) = {x ∈ R | f (x) = 0}. Prove
that R is surjective but not injective.

(36)b

In which of the following is (G, ∗) a semigroup? In which is it a group? Prove your answers.

G = N, a ∗ b = max{a, b}.
G = R \ { 1/2 }, a ∗ b = a − 2ab + b.

I know this is a lot of question but I'm really struggling and my test book doesn't have any examples. Thank you for all your time.

2. (2) b

$\displaystyle \phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}}$ (by p I mean prime)

Let q be a prime such that q|n

then: $\displaystyle \phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}}$

Where $\displaystyle \prod_{p|n}{\left(1-\frac{1}{p}\right)}$ includes the factor $\displaystyle \left(1-\frac{1}{q}\right)$ just once (1)

So $\displaystyle \phi(q\cdot{n})=q\cdot{n}\cdot{\prod_{p|(qn)}{\lef t(1-\frac{1}{p}\right)}}$

But, by (1) it must be $\displaystyle \prod_{p|(qn)}{\left(1-\frac{1}{p}\right)}=\prod_{p|n}{\left(1-\frac{1}{p}\right)}$ since q is already there and there are no new primes

Therefore: $\displaystyle \phi(q\cdot{n})=q\cdot{\phi(n)}$

(17) It follows by Fermat's Little Theorem that, since 101 is prime, $\displaystyle a^{100}\equiv{1}(\bmod.101)$ where $\displaystyle (a,101)=1$

Thus $\displaystyle 5^{100}\equiv{1}(\bmod.101)$

We have $\displaystyle 5\cdot{x}\equiv{31}(\bmod.101)$

Multiply both sides by $\displaystyle 5^{99}$

So: $\displaystyle x\equiv{3\cdot{5^{99}}}(\bmod.101)$

Now try to simplify this

3. Originally Posted by asw-88
...

(36)b

In which of the following is (G, ∗) a semigroup? In which is it a group? Prove your answers.

G = N, a ∗ b = max{a, b}.
G = R \ { 1/2 }, a ∗ b = a − 2ab + b.

I know this is a lot of question but I'm really struggling and my test book doesn't have any examples. Thank you for all your time.
this is just a direct application of the definition of a semigroup and a group.
which takes the role of the identity? is * associative? does every element of G has an inverse? you can do it! Ü

4. Originally Posted by asw-88
Just hoping for some help with my practice exam. Any help on any of the questions would be greatly appreciated as my lecturer is absolutely shocking. Cheers.

(2)b

Let n ∈ N and let p be a prime. Show that if p | n then φ(np) = pφ(n).
Hint: consider the prime factorisation of n.
this is my approach..

let $\displaystyle p$ be a prime such that $\displaystyle p|n$
let the factorization of n be denoted by

$\displaystyle n = p^e p_1^{e_1} p_2^{e_2}... p_k^{e_k}$

where $\displaystyle {e_i}'s$ are powers of the primes $\displaystyle {p_i}'s$ (and of course, $\displaystyle p$ is included in the factorization since $\displaystyle p|n$ and $\displaystyle e$ is the power of $\displaystyle p$ since it is arbitrary..)

so, $\displaystyle np = p^{e+1} p_1^{e_1} p_2^{e_2}... p_k^{e_k}$

now, we have $\displaystyle \varphi (n) = \varphi (p^e p_1^{e_1} p_2^{e_2}... p_k^{e_k}) = (p^{e-1})(p-1)\prod_{i=1}^k (p_i^{e_i-1})(p_i-1)$

so, $\displaystyle \varphi (np) = \varphi (p^{e+1} p_1^{e_1} p_2^{e_2}... p_k^{e_k}) = (p^e)(p-1)\prod_{i=1}^k (p_i^{e_i-1})(p_i-1)$

$\displaystyle = (p)(p^{e-1})(p-1)\prod_{i=1}^k (p_i^{e_i-1})(p_i-1) = p \, \varphi (n)$. QED..

5. Originally Posted by asw-88
(31)
Let P(R) be the set of all subsets of R; that is, P(R) = {X | X ⊆ R}. Let F be the set of all functions R → R. Define R : F → P(R) by R(f ) = {x ∈ R | f (x) = 0}. Prove
that R is surjective but not injective.
Clearly the function is not injective. $\displaystyle s(x) = x^2 \,\& \,i(x) = x$ then $\displaystyle F(i) = F(s)=\{0\}$.

The surjectivity is the hard part. Do you know about the characteristic function?
$\displaystyle \left( {\forall A \in P(\mathbb{R})} \right)\left[ {\chi _A :\mathbb{R} \to \mathbb{R}} \right]$ defined by $\displaystyle \chi _A (x) = \left\{ {\begin{array}{ll} {1,} & {x \in A} \\ {0,} & {x \notin A} \\ \end{array} } \right.$
If $\displaystyle M \in P(\mathbb{R})$ we must find a function $\displaystyle h:\mathbb{R} \to \mathbb{R}\,\& \,F(h) = M$.
Let $\displaystyle N = \mathbb{R}\backslash M$, that is the complement of $\displaystyle M$ in $\displaystyle \mathbb{R}$.
Now the claim is that $\displaystyle \chi _N$ is such a function.
Can you prove that?