elementary number theory - Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$

Prove that if $d$ divides $n$, then $2^d -1$ divides $2^n -1$.

Use the identity $x^k -1 = (x-1)*(x^{k-1} + x^{k-2} + \cdots + x +1)$

probability - Expectetion of $Y^{alpha}$ with $alpha >0$

Let $Y$ be a positive random variable. For $\alpha>0$ show that

$E(Y^{\alpha})=\alpha \int_{0}^{\infty}t^{\alpha -1}P(Y>t)dt$.

My ideas:

$E(Y^{\alpha})= \int_{-\infty}^{\infty}t^{\alpha}f_{Y}(t)dt$

=$\int_{0}^{\infty}t^{\alpha}f_{Y}(t)dt$

=$\int_{0}^{\infty}(\int_{0}^{t^{\alpha}}dy)f_{Y}(t)dt$

Answer

$E(Y^\alpha)=\int_0^\infty t^\alpha f_y(t)dt$. Let $G_y(t)=P(Y\gt t)=1-F_y(t)$. Therefore $G'_y(t)=-f_y(t)$. Integrate $E(Y^\alpha)$ by parts and get $E(Y^\alpha)=-t^\alpha G_y(t)\rbrack_0^\infty +\alpha \int_0^\infty t^{\alpha-1}G_y(t)dt={\alpha \int_0^\infty t^{\alpha-1}P(Y\gt t)dt}$.

calculus - Prove the series $sum_{n=1}^{infty} a_n$ converges iff $sum_{n=100}^{infty} a_n$ converges

I just had this problem on a final and I was confused about proving the reverse direction. For example, what if $a_n = \frac{1}{(n-1)^2}$?

Then $\sum_{n=100}^{\infty} a_n$ would converge, but the first term in $\sum_{n=1}^{\infty} a_n$ would be undefined.

I think I'm missing something. Any help would be appreciated.

number theory - Find all $n in mathbb{Z^+} : phi(n)=4$

I know that there is a similar post, but I m trying a different proof.
Also I will define $P$ be the set of all positive prime numbers.

Question: If $\phi$ is Euler's Phi Fuction, we want to find all $n \in \mathbb{Z^+} : \phi(n)=4$.

Answer: Let $n=p_1^{n_1}\cdot...\cdot p_k^{n_k}\in \mathbb{Z}^+$ be the factorization of $n$ in to primes. Then
$$\phi(n)=p_1^{n_1-1}\cdot ...\cdot p_k^{n_k-1}\cdot(p_1-1)\cdot...\cdot (p_k-1)=4$$

So, $\forall i \in \{1,2,...,k \} \implies p_i-1|4 $ . And from this, we have that

$$p_i-1\in\{1,2,4 \} \implies p_i\in \{2,3,5\} \in P$$
Now, we can see the primes that $n$ containts: $n=2^{n_1}3^{n_2}5^{n_3}, \ n_1,n_2,n_3 \in \mathbb{Z}^+$. So,
$$\phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4 \ (*)$$

The possible cases for $n_i$ are:

• $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively


• $n_2=1 \implies \phi(3)=2$


• $n_3=1 \implies \phi(5)=4$

All the posible combinations for the relation $(*)$ are $\phi(5),\ \phi(5)\phi(2),\ \phi(3)\phi(2^2),\ \phi(2^3)$. So, $n \in \{5,10,12,8\}.$

Is this completely right?

Thank you.

Answer

This seems to be completely correct to me.

algebra precalculus - Highest power of a prime $p$ dividing $N!$

How does one find the highest power of a prime $p$ that divides $N!$ and other related products?

Related question: How many zeros are there at the end of $N!$?

---

This is being done to reduce abstract duplicates. See Coping with *abstract* duplicate questions. and List of Generalizations of Common Questions for more details.

Answer

Largest power of a prime dividing $N!$

In general, the highest power of a prime $p$ dividing $N!$ is given by

$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

The first term appears since you want to count the number of terms less than $N$ and are multiples of $p$ and each of these contribute one $p$ to $N!$. But then when you have multiples of $p^2$ you are not multiplying just one $p$ but you are multiplying two of these primes $p$ to the product. So you now count the number of multiple of $p^2$ less than $N$ and add them. This is captured by the second term $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$. Repeat this to account for higher powers of $p$ less than $N$.

Number of zeros at the end of $N!$

The number of zeros at the end of $N!$ is given by $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ where $\left \lfloor \frac{x}{y} \right \rfloor$ is the greatest integer $\leq \frac{x}{y}$.

To make it clear, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ where $\alpha_i \in \mathbb{N}$.

Note that $\alpha_5 < \alpha_2$ whenever $N \geq 2$. (Why?)

The number of zeros at the end of $N!$ is the highest power of $10$ dividing $N!$

If $10^{\alpha}$ divides $N!$ and since $10 = 2 \times 5$, $2^{\alpha} | N!$ and $5^{\alpha} | N!$. Further since $\alpha_5 < \alpha_2$, the highest power of $10$ dividing $N!$ is the highest power of $5$ dividing $N!$ which is $\alpha_5$.

Note that there will be 

 1. A jump of $1$ zero going from $(N-1)!$ to $N!$ if $5 \mathrel\| N$

 2. A jump of $2$ zeroes going from $(N-1)!$ to $N!$ if $5^2 \mathrel\| N$

 3. A jump of $3$ zeroes going from $(N-1)!$ to $N!$ if $5^3 \mathrel\| N$ and in general

 4. A jump of $k$ zeroes going from $(N-1)!$ to $N!$ if $5^k \mathrel\| N$

where $a \mathrel\| b$ means $a$ divides $b$ and $\gcd\left(a,\dfrac{b}{a} \right)$ = 1.

Largest power of a prime dividing other related products

In general, if we want to find the highest power of a prime $p$ dividing numbers like $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$, $\displaystyle P(N,r)$, $\displaystyle \binom{N}{r}$, the key is to write them in terms of factorials.

For instance, $$\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1) = \frac{(2N)!}{2^N N!}.$$ Hence, the largest power of a prime, $p>2$, dividing $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ is given by $s_p((2N)!) - s_p(N!)$, where $s_p(N!)$ is defined above. If $p = 2$, then the answer is $s_p((2N)!) - s_p(N!) - N$.

Similarly, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle P(N,r)$ is given by $s_p(N!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.

Similarly, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle C(N,r)$ is given by $$s_p(N!) - s_p(r!) - s_p((N-r)!)$$ where $s_p(N!)$ is defined above.

algebra precalculus - Proof for formula for sum of sequence $1+2+3+ldots+n$?

Apparently $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$.

How? What's the proof? Or maybe it is self apparent just looking at the above?

PS: This problem is known as "The sum of the first $n$ positive integers".

Answer

Let $$S = 1 + 2 + \ldots + (n-1) + n.$$ Write it backwards: $$S = n + (n-1) + \ldots + 2 + 1.$$
Add the two equations, term by term; each term is $n+1,$ so
$$2S = (n+1) + (n+1) + \ldots + (n+1) = n(n+1).$$
Divide by 2: $$S = \frac{n(n+1)}{2}.$$

algebra precalculus - Proof for formula for sum of sequence $1+2+3+ldots+n$?

Apparently $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$.

How? What's the proof? Or maybe it is self apparent just looking at the above?

PS: This problem is known as "The sum of the first $n$ positive integers".