number theory and abstract algebra

**asw-88** · April 9th 2008, 03:13 AM

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.

**PaulRS** · April 9th 2008, 03:50 AM

(2) b

$\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: $\phi(n)=n\cdot{\prod_{p|n}{\left(1-\frac{1}{p}\right)}}$

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

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

But, by (1) it must be $\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: $\phi(q\cdot{n})=q\cdot{\phi(n)}$

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

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

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

Multiply both sides by $5^{99}$

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

Now try to simplify this

**kalagota** · April 9th 2008, 05:20 AM

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! Ü

**kalagota** · April 9th 2008, 05:36 AM

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 $p$ be a prime such that $p|n$
let the factorization of n be denoted by

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

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

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

now, we have $\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, $\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)$

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

**Plato** · April 9th 2008, 07:55 AM

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. $s(x) = x^2 \,\& \,i(x) = x$ then $F(i) = F(s)=\{0\}$ .

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

Thread: number theory and abstract algebra

LinkBack

Thread Tools

Display

number theory and abstract algebra

Similar Math Help Forum Discussions

Algebra help in Hardy's 'Intro to Number Theory'

Set Theory Abstract Algebra

terminology about ring/algebra in abstract algebra and measure theory

group theory abstract algebra

Algebra - Number Theory

Search Tags