divisibility - How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?

How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?

Answer

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$, $\forall N$. (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$.

So you will find that for $N \leq 24$, the number of zeros will be less than or equal to 4. However when $N$ hits $25$ you will get 2 additional zeros courtesy $25$ since $25 \times 2^2 = 100$. Hence, there will be a jump when you go from $24$ to $25$.

EDIT:

Note that there will be

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




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




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




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

where $a || b$ means $a$ divides $b$ and gcd($a,\frac{b}{a}$) = 1

EDIT

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$.

In case of the current example, the largest prime dividing $10$ is $5$. Hence, the largest power of $10$ dividing $N!$ is the same as the largest power of $5$ dividing $N!$.

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 (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 (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 (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.

abstract algebra - Proving that $left(mathbb Q[sqrt p_1,dots,sqrt p_n]:mathbb Qright)=2^n$ for distinct primes $p_i$.

I have read the following theorem:

If $p_1,p_2,\dots,p_n$ are distinct prime numbers, then$$\left(\mathbb Q\left[\sqrt p_1,\dots,\sqrt p_n\right]:\mathbb Q\right)=2^n.$$

I have tried to prove a more general statement but I have a problem at one point. (I still don't know how to prove the theorem above, too, because I don't know how not to use linear independence, which I do in the more general statement below.) Could you please help me overcome the obstacle I've encountered? I will post the intended proof and make it clear where I'm having trouble.

I want to prove the following statement:

Let $n\geq 1$. The set $B_n:=\left\{\sqrt {p_1^{\epsilon_1}}\sqrt {p_2^{\epsilon_2}}\cdots\sqrt {p_n^{\epsilon_n}}\,|\,(\epsilon_1,\epsilon_2,\cdots,\epsilon_n)\in\{0,1\}^n\right\}$ has $2^n$ elements and is a $\mathbb Q-$basis of $\mathbb Q\left[\sqrt p_1,\sqrt p_2,\cdots,\sqrt p_n\right].$

The proof will be by induction.

For $n=1,$ we have $B_n=\left\{1,\sqrt {p_1}\right\}.$ It is clear that $\sqrt{p_1}\neq 1,$ so the set has $2=2^1$ elements. It is the basis of $\mathbb Q[\sqrt{p_1}]$ because the minimal polynomial of $\sqrt {p_1}$ over $\mathbb Q$ has degree $2,$ and there is a theorem that $K[a]$ has $a^0,\cdots,a^{d-1}$ as a basis, where $d$ is the degree of the minimal polynomial of $a$ over $K$.

Suppose the statement is true for $n-1$, where $n\geq 2.$ We have

$$
\left(B_n=B_{n-1}\cup\sqrt{p_n}B_{n-1}\right)\text { and } \left(B_{n-1}\cap\sqrt{p_n}B_{n-1}=\emptyset\right),
$$

which is easy to see. It is also easy to see that $\operatorname{card}(B_{n-1})=\operatorname{card}(\sqrt{p_n}B_{n-1}),$ and therefore

$$
\operatorname{card}B_{n}=2^n.
$$

Let

$$
\sum_{x\in B_{n}}q_xx=0

$$

for some $\{q_x\}_{x\in B_n}\subset\mathbb Q.$ Let $p(x):=\sqrt{p_n}x$ for all $x\in B_{n-1}.$ We have

$$
\sum_{x\in B_{n}}q_xx=\sum_{x\in B_{n-1}} q_xx+\sum_{x\in \sqrt{p_n}B_{n-1}} q_xx=\sum_{x\in B_{n-1}} q_xx+\sum_{x\in B_{n-1}} q_{p(x)}\sqrt{p_n}x.
$$

Therefore

$$
\sum_{x\in B_{n-1}} q_xx=-\sqrt{p_n}\sum_{x\in B_{n-1}} q_{p(x)}x,\tag1
$$

and we can make the following division iff $q_{p(x)}\neq 0$ for all $x\in B_{n-1}$ (because $B_{n-1}$ is linearly indepentent over $\mathbb Q$):

$$
\sqrt{p_n}=-\frac{\sum_{x\in B_{n-1}} q_xx}{\sum_{x\in B_{n-1}} q_{p(x)}x},
$$

The right-hand side belongs to $\mathbb Q\left[\sqrt p_1,\sqrt p_2,\cdots,\sqrt p_{n-1}\right],$ so we have

$$
\sqrt{p_n}\in \mathbb Q\left[\sqrt p_1,\sqrt p_2,\cdots,\sqrt p_{n-1}\right].
$$

Therefore we can write $\sqrt{p_n}$ uniquely in the basis $B_{n-1}$.

$$
\sqrt{p_n}=\sum_{y\in B_{n-1}}c_yy

$$

for some $\{c_y\}_{y\in B_{n-1}}\subset \mathbb Q.$

After squaring this equation we will obtain

$$
p_n=\sum_{y\in B_{n-1}}c_y^2y^2+2\sum_{y,z\in B_{n-1}}c_yc_zyz.
$$

The last sum must be zero because it is not in $\mathbb Q$ and because after reducing it, we obtain a representation of $p_n$ in the basis $B_{n-1},$ which is unique. Thus

$$p_n=\sum_{y\in B_{n-1}}c_y^2y^2.$$

Unfortunately, I can't prove that $c_yc_z$ is always zero. This was my first thought, but clearly there's trouble with the possibility of reductions in
$$
\sum_{y,z\in B_{n-1}}c_yc_zyz.
$$

Different pairs $y,z$ may yield the same element of $B_{n-1}$ in the product $yz.$ This happens for example when $y=\sqrt 5\sqrt 3,$ $z=\sqrt 5\sqrt 2,$ and $y'= \sqrt 11\sqrt 2,$ $z'=\sqrt 11\sqrt 3$.

If it were true that $c_yc_z$ is always zero, I would be able to continue my proof as follows. We would have only one $y_0$ such that $c_{y_0}\neq 0$ and we'd get

$$p_n=c_{y_0}^2y_0^2.$$

Let $c_{y_0}=\frac kl$. We can write
$$l^2p_n=k^2y_0^2.$$

But $y_0^2$ is the product of some primes different from $p_n$. Therefore the greatest power of $p_n$ that divides the right-hand side is even. However, the greatest power of $p_n$ that divides the left-hand side is odd. A contradiction.

The contradiction proves that $q_{p(x)}=0$ for all $x\in B_{n-1}.$ Hence $(1)$ gives us that

$$
\sum_{x\in B_{n-1}} q_xx=0
$$

and linear independence of $B_{n-1}$ gives us that $q_x=0$ for all $x\in B_{n-1}.$

This gives us that $B_n$ is linearly independent. It generates the whole $\mathbb Q\left[\sqrt p_1,\sqrt p_2,\cdots,\sqrt p_n\right]$ because

$$
\mathbb Q\left[\sqrt p_1,\sqrt p_2,\cdots,\sqrt p_n\right]=\left(\mathbb Q\left[\sqrt p_1,\sqrt p_2,\cdots,\sqrt p_{n-1}\right]\right)\left[\sqrt{p_n}\right].
$$

This would end the proof.

Answer

HINT $\ $ An inductive proof follows easily from this

LEMMA $\rm\ \ [K(\sqrt{a},\sqrt{b}) : K] = 4\ $ if $\rm\ \sqrt{a},\ \sqrt{b},\ \sqrt{a\:b}\ $ all are not in $\rm\:K\:$ and $\rm\: 2 \ne 0\:$ in $\rm\:K\:.$

Proof $\ \ $ Let $\rm\ L = K(\sqrt{b})\:.\:$ Then $\rm\: [L:K] = 2\:$ via $\rm\:\sqrt{b} \not\in K\:,\:$ so it is sufficient to prove $\rm\: [L(\sqrt{a}):L] = 2\:.\:$ It fails only if $\rm\:\sqrt{a} \in L = K(\sqrt{b})\ $ and then $\rm\ \sqrt{a}\ =\ r + s\ \sqrt{b}\ $ for $\rm\ r,s\in K\:.\:$ But that is impossible since squaring yields $\rm(1):\ \ a\ =\ r^2 + b\ s^2 + 2\:r\:s\ \sqrt{b}\:,\: $ which contradicts hypotheses as follows:

$\rm\qquad\qquad rs \ne 0\ \ \Rightarrow\ \ \sqrt{b}\ \in\ K\ \ $ by solving $(1)$ for $\rm\sqrt{b}\:,\:$ using $\rm\:2 \ne 0$

$\rm\qquad\qquad\ s = 0\ \ \Rightarrow\ \ \ \sqrt{a}\ \in\ K\ \ $ via $\rm\ \sqrt{a}\ =\ r \in K$

$\rm\qquad\qquad\ r = 0\ \ \Rightarrow\ \ \sqrt{a\:b}\in K\ \ $ via $\rm\ \sqrt{a}\ =\ s\ \sqrt{b}\:,\: \ $times $\rm\:\sqrt{b}\quad\quad$ QED

Using the above as the inductive step one easily proves the following result of Besicovic.

THEOREM $\ $ Let $\rm\:Q\:$ be a field with $2 \ne 0\:,\:$ and $\rm\ L = Q(S)\ $ be an extension of $\rm\:Q\:$ generated by $\rm\: n\:$ square roots $\rm\ S = \{ \sqrt{a}, \sqrt{b},\ldots \}$ of elts $\rm\ a,\:b,\:\ldots \in Q\:.\:$
If every nonempty subset of $\rm\:S\:$ has product not in $\rm\:Q\:$ then each successive
adjunction $\rm\ Q(\sqrt{a}),\ Q(\sqrt{a},\:\sqrt{b}),\:\ldots$ doubles the degree over $\rm\:Q\:,\:$ so, in total, $\rm\: [L:Q] \ =\ 2^n.\:$ Hence the $\rm2^n$ subproducts of the product of $\rm\:S\:$ comprise a basis of $\rm L$ over $\rm\:Q\:.$

calculus - Can you take the derivative of a function at infinity?

Exactly the title: can you take the derivative of a function at infinity?

I asked my maths teacher, and while she thought it was an original question, she didn't know the answer, and I couldn't find anything online about this.

Maybe this is just me completely misunderstanding derivatives and functions at infinity, but to me, a high schooler, it makes sense that you can. For example, I'd imagine that a function with a horizontal asymptote would have a derivative of zero at infinity.

Answer

In a very natural sense, you can! If $\lim_{x \to \infty} f(x) = \lim_{x \to -\infty} f(x) = L$ is some real number, then it makes sense to define $f(\infty) = L$, where we identify $\infty$ and $-\infty$ in something called the one-point compactification of the real numbers (making it look like a circle).

In that case, $f'(\infty)$ can be defined as

$$f'(\infty) = \lim_{x \to \infty} x \big(f(x) - f(\infty)\big).$$
When you learn something about analytic functions and Taylor series, it will be helpful to notice that this is the same as differentiating $f(1/x)$ at zero.

Notice that this is actually not the same as $\lim_{x \to \infty} f'(x)$.

These ideas actually show up quite a bit in analytic capacity, so this is a rather nice idea to have.

---

I wanted to expand this answer a bit to give some explanation about why this is the "correct" generalization of differentiation at infinity. and hopefully address some points raised in the comments.

Although $\lim_{x \to \infty} f'(x)$ might feel like the natural object to study, it is quite badly behaved. There are functions which decay very quickly to zero and have horizontal asymptotes, but where $f'$ is unbounded as we tend to infinity; consider something like $\sin(x^a) / x^b$ for various $a, b$. Furthermore, $\lim_{x \to \infty} f'(x) = 0$ is not sufficient to guarantee a horizontal asymptote, as $\sqrt{x}$ shows.

So why should we consider the definition I proposed above? Consider the natural change of variables interchanging zero and infinity*, swapping $x$ and $1/x$. Then if $g(x) := f(1/x)$ we have the relationship

$$\lim_{x \to 0} \frac{g(x) - g(0)}{x} = \lim_{x \to \infty} x \big(f(x) - f(\infty)\big).$$

That is to say, $g'(0) = f'(\infty)$. Now via this change of variables, neighborhoods of zero for $g$ correspond to neighborhoods of $\infty$ for $f$. So if we think of the derivative as a measure of local variation, we now have something that actually plays the correct role.

Finally, we can see from this that this definition of $f'(\infty)$ gives the coefficient $a_1$ in the Laurent series $\sum_{i \ge 0} a_i x^{-i}$ of $f$. Again, this corresponds to our idea of what the derivative really is.

* This is one of the reasons why I used the one-point compactification above. Otherwise, everything that follows must be a one-sided limit or a one-sided derivative.

trigonometry - Does atan2(mean sine, mean cosine) approximate the mean angle?

I need to find an approximation for the sine and cosine of a rotation angle $\bar{\theta}$ such that:

$\bar{\theta} = \frac{1}{n}\sum\limits_{i=1}^{n}\theta_i$

I know each $s_i = \sin(\theta_i)$ and $c_i = \cos(\theta_i)$

But I want to do it without using $\arcsin(\theta_i)$ or $\arccos(\theta_i)$

---

My current approach is to get the mean sines and cosines; and normalize them:

$\sin(\tilde{\theta}) = \frac{1}{\alpha \,n}\sum s_i$

$\cos(\tilde{\theta}) = \frac{1}{\alpha \,n}\sum c_i$

choose $\alpha$ such that

$\sin(\tilde{\theta})^2 + \cos(\tilde{\theta})^2 = 1$

---

If I am not mistaken, what I get from this is

$\tilde{\theta} = \text{atan2}\left(\frac{1}{n}\sum s_i\,,\frac{1}{n}\sum c_i\right)$

I want to know if this actually approximates $\bar{\theta}$ for any set of values $\theta_i$

---

What I have tried

For the particular case where $\forall i; \;\theta_i\in\left]-\frac{\pi}{2},\frac{\pi}{2}\right[$

$\forall i; \;\cos(\theta_i)>0$

$\tan(\tilde{\theta}) = \frac{A}{B}; \; B>0$

By adding a new $\theta_k$ we have

$\tan(\tilde{\theta})^* = \frac{A+\frac{1}{n}s_k}{B+\frac{1}{n}c_k} = \frac{n\,A+s_k}{n\,B+c_k}$

$\frac{s_k}{c_k} = \frac{A}{B} \Rightarrow \frac{s_k}{c_k} = \tan(\tilde{\theta})^* = \frac{A}{B}$

$\frac{s_k}{c_k} > \frac{A}{B} \Rightarrow \frac{s_k}{c_k} > \tan(\tilde{\theta})^* > \frac{A}{B}$

$\frac{s_k}{c_k} < \frac{A}{B} \Rightarrow \frac{s_k}{c_k} < \tan(\tilde{\theta})^* < \frac{A}{B}$

So if every angle is between $-90^o$ and $90^o$ my approximation give a consistent result. (I think it works as well for angles between $90^o$ and $270^o$)

But how about the general case? When we can not assume the signs of $\sin(\theta_i)$ and $\cos(\theta_i)$? And when the tangent function is not monotonic?

Answer

I think you got it. To get an average angle, do not do $\frac{1}{n} \sum_i^n \theta_i$ but use the atan2() function with the average sine and cosine.

This is equivalent to take a scatter plot of points, finding their "center of mass" (or barycenter) and drawing an angle from the origin to the COM.

$$\tilde{\theta} = {\rm atan2}\left( \sum_i^n y_i, \sum_i^n x_i \right)$$

In the extreme case that $\tilde{x} \approx 0$ and $\tilde{y} \approx 0$ that average angle is going to have lots of uncertainty associated with it. This is because the scatter of points is near the origin and the location angle isn't well defined.

calculus - Who introduced the term indefinite integral and the notation $int f(x)dx$?

I find the notation $\int f(x)dx$ for the indefinite integral of $f(x)$ on some interval $I$ is both suggestive and confusing. On the one hand, this notation is very suggestive when we calculate the indefinite integral either by the change of variable formula or the integration by parts formula. On the other hand, this notation looks very likely with the definite integral notation $\int_a^b f(x)dx$. But these two terms arise from different backgrounds, one to find the primitive while the other to find the area.

I want to know who introduced the term indefinite integral and the notation $\int f(x)dx$ and why?

elementary set theory - Is this proof correct for : Does $F(A)cap F(B)subseteq F(Acap B) $ for all functions $F$?

Is this proof correct? To prove $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$.

Let any number $y\in F(A)\cap F(B)$. We want to show $y\in F(A\cap B).$

Therefore, $y\in F(A)$ and $y\in F(B)$, by definition of intersection.

By definition of inverse, $y=F(x)$ for some $x\in A$ and $x\in B$

And so, $y=F(x)$ for some $x\in A\cap B$

And therefore, $y\in F(A\cap B)$

I have a gut feeling deep down that something is wrong. Can anyone help me pinpoint the mistake? I am not sure why am I having so much problems with functions. Am I not thinking in the right direction?

Sources : 2nd Ed, P219 9.60 = 3rd Ed, P235 9.12, 9.29 - Mathematical Proofs, by Gary Chartrand,
P214 Theorem 12.4 - Book of Proof, by Richard Hammack,
P257-258 - How to Prove It, by D Velleman.

Answer

The third line is mistaken. You only know that there exists an $x$ in $A$ such that $F(x)=y$, and you know there is a $z\in B$ such that $F(z)=y$.

It is extremely easy to find a counterexample: just draw two sets $A$, $B$ that are disjoint, and map an $a\in A$ and a $b\in B$ to a single point. Then you have that $y\in F(A)\cap F(B)$, but $F(A\cap B)=\emptyset$.

elementary set theory - Why is $|Y^{emptyset}|=1$ but $|emptyset^Y|=0$ where $Yneq emptyset$

I have a question about the set of functions from a set to another set. I am wondering about the degenerate cases. Suppose $X^Y$ denotes the set of functions from a set $Y$ to a set $X$, why is $|Y^{\emptyset}|=1$ but $|\emptyset^Y|=0$ where $Y\neq \emptyset$?

Answer

The definition of $A^B$ is "the set of all functions with domain $B$ and codomain $A$".

A function $f$ from $B$ to $A$ is a set of ordered pairs such that:

1. If $(x,y)\in f$, then $x\in B$ and $y\in A$.



2. For every $b\in B$ there exists $a\in A$ such that $(b,a)\in f$.


3. If $(b,a)$ and $(b,a')$ are in $f$, then $a=a'$.

Now, what happens if $B=\emptyset$? Well, then there can be no pair in $f$, because you cannot have $x\in B$. But notice that in that case, 2 is satisfied "by vacuity" (if it were false, you would be able to exhibit a $b\in\emptyset$ for which there is no $a\in A$ with $(b,a)\in f$; but there are no $b\in\emptyset$, so you cannot make such an exhibition; the statement is true because the premise, "$b\in\emptyset$", can never hold). Likewise 3 holds by vacuity. So it turns out that if we take $f=\emptyset$, then $f$ satisfies 1, 2, and 3, and therefore it is by all rights a "function from $\emptyset$ to $A$". But this is the only possible function from $\emptyset$ to $A$, because only the empty set works.

By contrast, if $A=\emptyset$, but $B\neq\emptyset$, then no set $f$ can satisfy both 1 and 2, so no set can be a function from $B$ to $A$.

That means that $Y^{\emptyset}$ always contains exactly one element, namely the "empty function", $\emptyset$. But if $Y\neq\emptyset$, then $\emptyset^Y$ contains no elements; that is, it is empty.

Therefore, since $Y^{\emptyset}$ has exactly one element, $|Y^{\emptyset}|=1$ regardless of what $Y$ is. But if $Y\neq\emptyset$, then $\emptyset^{Y}$ is empty, so $|\emptyset^{Y}| = 0$.