Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I just need a small hint, not the full answer. I know that, if $f$ is a morphism,

  1. $a \mid b \implies f(a) \mid f(b)$
  2. $a \mid b$ and $a \mid c \implies a \mid b+c$, so $f(a) \mid f(b), f(a) \mid f(c), f(a) \mid f(b + c)$. Also, $f(a) \mid f(b) + f(c)$
  3. $\forall a \in \mathbb{N}, a \mid 0$, so $\forall a \in \mathbb{N}, f(a) \mid f(0)$
  4. $\forall a \in \mathbb{N}, 1 \mid a$, so $\forall a \in \mathbb{N}, f(1) \mid f(a) $

From these I can draw some conclusions:

a. From 3., $f(0) = a$ ($a \neq 0$), $f(\mathbb{N})$ only contains divisors of $a$.

b. From 4., if $f(1) = a$, then $f(\mathbb{N})$ only contains multiples of $a$.

The most general form I can think of for f is this:

$f(x) = ax^{b} (a, b \in \mathbb{N})$, but I can't seem to go any further than this.

Any help is appreciated.

share|cite|improve this question
$f(x) = ax^b$ for b > 1 may not satisfy condition 2. – Isomorphism Dec 15 '12 at 12:20
@Isomorphism can you give me an example for that? My reasoning is that if $x \mid a$ and $x \mid b$, then $x \mid a + b$, which means that $a+b = kx (k \in \mathbb{N})$. But then $(a+b)^r = (kx)^r = k^rx^r$ and $x^r \mid k^rx^r$. (I removed the other constant to make this simpler, it doesn't change anything) Is this wrong? – Gabi Purcaru Dec 15 '12 at 12:33
You were right and I was wrong. We can prove the second property for $f(x) = ax^b$ by looking at the prime divisors. Anyway, another solution is the constant map. Let $c$ be a natural number.Define $f(x) = c$. This works too. – Isomorphism Dec 15 '12 at 12:36
@Isomorphism but isn't this just $f(x) = cx^0$ ? Anyway, I'm not convinced that these are the only morphisms either, because, for example, $f(0)=0$ and $\forall x > 0$, $f(x) = c$, or $f(0) = 8, f(1) = 2, f(2) = 4, f(x) = 8 $ for any other $x$, etc. are valid morphisms. – Gabi Purcaru Dec 15 '12 at 12:39
Ah! correct!. But f(1) = 1. For if $f(1) = x > 1$, then since $1^n|a$ for all n, we must have $x^n | f(a)$ for all n. But since $x > 1$, eventually $x^n$ should grow beyond $f(a)$. Thats a contradiction to the claim $f(1^n) | f(a)$ – Isomorphism Dec 15 '12 at 12:42
up vote 3 down vote accepted

Your observations a,b are fine so far (if $0\in\mathbb N$ at all, that may depend on your local definitions).

Note that $a|b$ with $a>b$ is only possible with $b=0$. This allows us to construct uncountably many morphisms $f$ with $f(0)=0$: Assume $n\in\mathbb N$ and we have selected $a_k$ for $0\le k<n$ such that $a_0=0$ and $0< r,s\le n$ with $r|s$ implies $a_r|a_s$. Select $$\tag1a_{n}\in\bigcap_{0<k<n\atop k|n} a_k\mathbb N$$ arbitrarily (which is possible as the set on the right contains at least $0$). By the choice we guarantee that $k|n$ implies $a_k|a_n$. Therefore, for any such sequence $(a_n)$, letting $f(n)=a_n$ gives us a morphism. Note that any morphism with $f(0)=0$ can be obtained this way, i.e. the restriction imposed by $(1)$ is necessary.

For morphisms with $f(0)>0$ you correctly observed that we need $f(n)|f(0)$ for all $n$, esp. $f(n)\ne 0$ for all $n$. We can do almost the same as above, more precisely select $$\tag2 a_{n}\in\{d\in\mathbb N\colon d|f(0)\}\cap\bigcap_{0<k<n\atop k|n} a_k\mathbb N$$ this time observing that the set in $(2)$ is nonempty because it contains $f(0)$. However, at each step there are only finitely many choices. Still, this gives another uncountable lot of morphisms (why?) if $f(0)>1$.

share|cite|improve this answer
$0 \in \mathbb{N}$, yes. Sorry for the confusion... This being my homework, I figured I was missing something, but now I'm starting to think the teacher was messing with us. Thanks! – Gabi Purcaru Dec 15 '12 at 13:12

It's a big hairy beast.

At all times, we will assume the prime factorization of $n$ is $n=p_1^{a_1}...p_k^{a_k}$.

For example, define a function first for each prime power, and then you can define $\phi(n)=\phi(p_1^{a_1})...\phi(p_k^{a_k})$. That only gives some basic examples, hardly begins to scratch the surface, but the restriction of $\phi$ at any prime power can be almost anything. (You can't define it arbitrarily for prime powers - for each $p^a$ you can choose $\phi(p^a)/\phi(p^{a-1})$ arbitrarily.)

One non-trivial example is to define $\phi(n) = p_1p_2...$. In this case your result is always square-free. Indeed, the function returns the largest square-free divisor of $n$.

Another non-trivial example would "forget" the power of $2$ is the prime factorization: $\phi(n)$ is the largest odd factor of $n$.

These first two examples preserve $\gcd$ and $\operatorname{lcm}$, which are the meet and join operator of $(\mathbb N,\mid)$.

Another example would be $\phi(n)=x^{\max(a_1,...a_k)}$, for some fixed $x\in\mathbb N$. This does not preserve $\gcd$, I don't think.

It might be worth just looking at examples that only depend on two primes. So morphisms $\phi$ such that $\phi(2^{a_1}3^{a_2}p_3^{a_3}...p_k^{a_k})=\phi(2^{a_1}3^{a_2})$ for all values. Even that is going to be an interesting mess.

share|cite|improve this answer
thanks for your input. I selected Hagen's answer because it describes all solutions though – Gabi Purcaru Dec 16 '12 at 7:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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