Show that $\varphi(m)|\varphi(n) $ whenever $m|n$.  I  am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of $m$.  $$ \varphi(n)=n\prod_{i=1}^{k}\Bigl(1-\frac{1}{p_{i}}\Bigr)  $$
27132
I want to prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.  It's given that $d \mid n$, so we know that $n = dm$, for some $m \in \mathbb{Z}$. Now, I want to show that $\varphi(d) \mid \varphi(n)$, i.e. that $\varphi(n) = k\varphi(d)$, for some $k \in \mathbb{Z}$. Drawing a blank of where to go from here.
33322
Let $a$ and $b$ be nonzero integers. Prove that $a$ divides $b$ and $b$ divides $a$ if and only if $a = \pm b$.   Since this is a iff statement, I need to prove it both ways:  $\Rightarrow$ If $a=\pm b$, then  $a$ divides $b$ and $b$ divides $a$;  and  $\Leftarrow$ If $a$ divides $b$ and $b$ divides $a$, then $a=\pm b$.  I tried to prove it but I don't know how to manage the $\pm$ sign, can anyone give me a hit or suggestion to start this proof?  Thanks
99967
For a positive integer $n$, prove that: $$\sum_{d\mid n} (-1)^{n/d} \cdot \varphi(d) = \begin{cases} 0 &amp; \text{if $n$ is even}  \\ -n  &amp; \text{if $n$ is odd}  \end{cases}$$  I can't even think, how, to begin with, this problem, please provide easy proof of this.
69082
In , $\exists$ this exercise.  Let $s &gt; 1$ and let $\zeta(s) = \sum_{n=1}^\infty n^{-s}$.  Let $X$ and $Y$ be independent $\mathbb{N}$-valued random variables with $P(X=n)=P(Y=n)=\dfrac{n^{-s}}{\zeta(s)}$.  Facts:  1 The events ($E_p$: $p$ prime) where $E_p =$ ($X$ is divisible by $p$) (This time $p$ may not be prime) are independent.  2 The events ($F_p$: $p$ prime) where $F_p =$ ($Y$ is divisible by $p$) (This time $p$ may not be prime) are independent.  3 $P(E_p) = p^{-s}$  4 This is Euler's formula $1/\zeta(s) = \prod_p (1-1/p^s)$ where $p$ is prime.  5 $P(X=1) = 1/\zeta(s) = \prod_p (1-1/p^s)$  6 $P(\text{no square other than 1 divides }X)= \dfrac{1}{\zeta(2s)}$  Here is the exercise:  Let $H$ be the highest common factor of $X$ and $Y$. Prove that $P(H=n) = \dfrac{n^{-2s}}{\zeta(2s)}$.  How do I go about doing this? I know $H$ divides both $X$ and $Y$ but that's just making use of the fact that $H$ is a common factor. Since it is the highest, all the natural numbers greater than $H$ do not divide $X$ and $Y$ or something like that?
599
This an interesting problem my friend has been working on for a while now (I just saw it an hour ago, but could not come up with anything substantial besides some PMI attempts).  Here's the full problem:  Let $x_{1}, x_{2}, x_{3}, \cdots x_{y}$ be all the primes that are less than a given $n&gt;1,n \in \mathbb{N}$.   Prove that $$x_{1}x_{2}x_{3}\cdots x_{y} &lt; 4^n$$  Any ideas very much appreciated!
49659
Can anyone help me out here? Can't seem to find the right rules of divisibility to show this:  If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.
19988
What is the meaning of $$ \\\frac{m}{n}\equiv k\pmod l $$ and $$ \\\frac{m}{n} \mod l $$ $m, n, k, l \in\mathbb N$ and $\gcd(m, n)=1$.
83266
For any positive integer $n$, let $\mathrm{PF}(n)$ denote the set of all distinct prime factors of $n$ (not counted with multiplicity).  The question (using the above notation) is: Is it true that for any two positive integers $m$ and $n$, $\phi(mn)=m\phi(n)$ if and only if $\mathrm{PF}(m) \subseteq \mathrm{PF}(n)$, where $\phi$ is the totient function?  Hint for the if direction: Any prime factor of $mn$ must either be a prime factor of $m$ or a prime factor of $n$ (by Euclid's lemma). But since any prime dividing $m$ also divides $n$, $mn$ has the same distinct prime factors as $n$, and hence any integer coprime to one of them is also coprime to the other.  Note that it is possible for $\mathrm{PF}(m) \subseteq \mathrm{PF}(n)$ to be true while $m \not\mid n$. For example, $4 \not\mid 2$, but they both have $2$ as the only prime factor. In this case, $\phi(8)=4=4 \cdot 1=4\phi(2)$.
17137
In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while now but to no avail and would be grateful if you could help me.
78044
I do not know how to prove this question: $m^{\phi(n)}+n^{\phi(m)}\equiv 1 \pmod {mn}$ where $m$ and $n$ are relatively prime.  Can anyone help?
101211
Let $\varphi(n)$ denotes the cardinality of the set $\{a | 1\le a\le n, (a,n)=1\}$ where $(a , n)$ denotes the gcd of $a$ and $n$. Which of the following is NOT true ? $(a)$ There exist infinitely many $n$ such that $\varphi (n)\gt \varphi(n+1)$ $(b)$ There exist infinitely many $n$ such that $\varphi (n)\lt \varphi(n+1)$ $(c)$ There exist $N\in \mathbb{N}$ such that $N\gt 2$ and for all $n\gt N$,  $\varphi (N)\lt \varphi(n)$ $(d)$ The set $\{ \frac {\varphi (n)}{n} : n\in \mathbb{N} \} $ has finitely many limit points.  My Thinking: $(a)$ is true  by selecting $n=p$  ( an odd prime greater than $3$) Justification: Since $p$ is odd, $p+1$ is even. Now $\varphi(p)=p-1$ and $\varphi(p+1)\le p+1-\frac{p+1}{2}=\frac{p+1}2$ So $\varphi(p+1)\le \frac{p+1}2 \lt p-1=\varphi(p)$ By the infinitudes of primes, the result follows. $(b)$ Is true by taking $n=p-1$ where $p$ is an odd prime greater than $3$ and following the same line of reasoning. $(c)$ This statement (if true ) means that the set $\{\varphi(n) : n\gt N\}$ is bounded below. I think it is true My argument : Let $N=6$ . Then $\varphi(6)=2$ If $n\gt 6$ and is prime  , then clearly $\varphi(n)\gt 2$ Otherwise, if $n$ is composite, then let $n=p_1^{r_1} p_2^{r_2}...p_k^{r_k}$ . $\varphi(n)=p_1^{r_1-1}p_2^{r_2-1}...p_k^{r_k-1}(p_1-1)(p_2-1)..(p_k-1)$ If $\phi(n)=2$ , then the distinct primes can be just $2$ and $3$. So the above equality reduces to $2=\phi(n)=2^{r_1}3^{r_2-1}$  when both the factors $2$ and $3$ are present . This gives $r_1=r_2=1$ and so $n=6$ When only $3$ present ,  then we get $n=3$ and if the factor is only $2$ , then $n=4$. So the result follows as $N=6$ works $(d)$ This is NOT true. Justification :- Let $\{p_i\}$ be the enumeration of primes. Let an index $k$ be fixed and $i$ be the running index. Then if the only prime factors of  $n_i$ are $p_k, p_i$ , then $\frac{\varphi(n_i)}{n_i}=\big( 1-1/p_k\big)\big(1-1/p_i\big)$ So ,letting $i\to \infty$, we have $\lim_{i\to \infty}\frac{\varphi(n_i)}{n_i}=1-1/{p_k}$ Since $p_k$ is arbitrary, there are infinitely many limit points (maybe uncountably many) limits points of the given set. Please check if my work is correct or the answers can be shortened in any way. Thanks for your time.
119971
Prove that $\mathbb Z_{m}\times\mathbb Z_{n} \cong \mathbb Z_{mn}$ implies $\gcd(m,n)=1$.  This is the converse of the Chinese remainder theorem in abstract algebra. Any help would be appreciated.  Thanks!
72511
This is my first question.   Let $a_1, a_2,\ldots, a_k$ be natural numbers $\leq n$ with $m$ prime factors.  Let $p_1, p_2, \ldots, p_r$ be the prime numbers $\leq n$.   Let $$C_{m,n} = \frac{\sum_{i=1}^{k}a_i}{\sum_{i=1}^{r}p_i}$$ Does the following limit exist when $m\geq 2$? Obviously, when $m=1$,  $C_{1,n}=1$.  $$\lim_{n\to \infty} C_{m,n}$$  I have some guesses but not defendable enough.  My best,  The FM.
36335
I need to show that if $(n-2)! \equiv 1 \pmod n$ then $n$ is prime. I think that if $n$ is composite, then we'll have every factor of $n$ in $(n-2)!$, and it would yield that $(n-2)! \equiv 0 \pmod n$. However, I didn't use the fact that it specifically congruent to $1 \bmod n$, so I think I'm getting something fundamental wrong. Is my solution correct? Why do we demand congruence to $1 \bmod n$?
119044
Let   $\varphi(n)$ be the totient-function  $\sigma(n)$ be the divisor-sum-function    It is clear that every prime number $n$ is the arithmetic mean of $\varphi(n)$ and $\sigma(n)$, in other words , the equality $$\varphi(n)+\sigma(n)=2n$$ holds.      Can the given equality hold for a composite number $n$ ?   Upto $10^8$, I did not find an example. I conjecture that the equality can only hold for primes or $n=1$. How can I prove it ?
40705
I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof  I tried saying by the division algorithm the prime factor is either the form 3m,3m+1,3m+2.  Case 1: $3m$      suppose $3m$ does divide $3n+2$. That means $3mr=3n+2$ where $r$ is some integer. But we get $mr-n= 2/3$ and since $mr-n$ is an integer that's a contradiction. Thus $3m$ does not work.  Case 2: $3m+1$ Same argument here  Case 3: $3m+2$ By the fundamental theorem of arithmetic every integer is divisible by a prime. But not sure what to do from here.
52795
Let $n$ be an integer, prove that every prime factor of $12x^2+1$ has the form $6m+1$, where $m$ is an integer.  I've gone as far as knowing that all primes $p&gt;3$ are either $6m+1$ or $6m-1$, how do I use this, not sure whether to even use that.  I know about the Legendre symbol and quadratic reciprocity