All Questions
159,920
questions
100
votes
9
answers
10k
views
Congruence Arithmetic Laws, e.g. in divisibility by $7$ test
I have seen other criteria for divisibility by $7$. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. $323$) is interesting, but could not prove it.
Let $n = (...
- 5,215
438
votes
23
answers
77k
views
How can I evaluate $\sum_{n=0}^\infty(n+1)x^n$?
How can I evaluate
$$\sum_{n=1}^\infty\frac{2n}{3^{n+1}}$$?
I know the answer thanks to Wolfram Alpha, but I'm more concerned with how I can derive that answer. It cites tests to prove that it is ...
- 4,595
129
votes
12
answers
23k
views
Modular exponentiation by hand ($a^b\bmod c$)
How do I efficiently compute $a^b\bmod c$:
When $b$ is huge, for instance $5^{844325}\bmod 21$?
When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for ...
- 47.9k
183
votes
8
answers
90k
views
How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression?
How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression? For example here is the sum of $\cos$ series:
$$\sum_{k=0}^{n-1}\cos (a+k \cdot d) =\frac{\sin(n \times \frac{...
- 21.7k
535
votes
29
answers
209k
views
How to prove that $\lim\limits_{x\to0}\frac{\sin x}x=1$?
How can one prove the statement
$$\lim_{x\to 0}\frac{\sin x}x=1$$
without using the Taylor series of $\sin$, $\cos$ and $\tan$? Best would be a geometrical solution.
This is homework. In my math ...
- 8,939
8
votes
3
answers
6k
views
Mod of numbers with large exponents [modular order reduction]
I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two:
$13^{100} \bmod 7$
$7^{100} \bmod 13$
I've also heard of the Congruence ...
- 231
187
votes
14
answers
17k
views
Why $\sqrt{-1 \cdot {-1}} \neq \sqrt{-1}^2$?
I know there must be something unmathematical in the following but I don't know where it is:
\begin{align}
\sqrt{-1} &= i \\\\\
\frac1{\sqrt{-1}} &= \frac1i \\\\
\frac{\sqrt1}{\sqrt{-1}} &...
- 2,073
1251
votes
26
answers
133k
views
Is $\frac{\textrm{d}y}{\textrm{d}x}$ not a ratio?
In Thomas's Calculus ($11$th edition), it is mentioned (Section $3.8$ pg $225$) that the derivative $\displaystyle{\frac{dy}{dx}}$ is not a ratio. Couldn't it be interpreted as a ratio, because ...
- 15.6k
377
votes
35
answers
127k
views
If $AB = I$ then $BA = I$
If $A$ and $B$ are square matrices such that $AB = I$, where $I$ is the identity matrix, show that $BA = I$.
I do not understand anything more than the following.
Elementary row operations.
Linear ...
- 5,905
816
votes
50
answers
131k
views
The Basel problem
As I have heard people did not trust Euler when he first discovered the formula (solution of the Basel problem)
$$\zeta(2)=\sum_{k=1}^\infty \frac{1}{k^2}=\frac{\pi^2}{6}$$
However, Euler was Euler ...
22
votes
5
answers
8k
views
Solving linear congruences by hand: modular fractions and inverses
When I am faced with a simple linear congruence such as
$$9x \equiv 7 \pmod{13}$$
and I am working without any calculating aid handy, I tend to do something like the following:
"Notice" that adding $...
- 19.3k
172
votes
10
answers
46k
views
Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$
For all $a, m, n \in \mathbb{Z}^+$,
$$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
Juan Liner
30
votes
4
answers
54k
views
Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$
I want to find the number of nonnegative integer solutions to
$$x_1+x_2+x_3+x_4=22$$
which is also the number of combinations with replacement of $22$ items in $4$ types.
How do I apply stars and bars ...
85
votes
5
answers
32k
views
How to use the Extended Euclidean Algorithm manually?
I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
- 2,257
57
votes
14
answers
21k
views
How to prove that $\log(x)<x$ when $x>1$?
It's very basic but I'm having trouble to find a way to prove this inequality
$\log(x)<x$
when $x>1$
($\log(x)$ is the natural logarithm)
I can think about the two graphs but I can't find ...
- 2,417
347
votes
31
answers
57k
views
Is it true that $0.999999999\ldots=1$?
I'm told by smart people that
$$0.999999999\ldots=1$$
and I believe them, but is there a proof that explains why this is?
140
votes
1
answer
28k
views
Overview of basic facts about Cauchy functional equation
The Cauchy functional equation asks about functions $f \colon \mathbb R \to \mathbb R$ such that
$$f(x+y)=f(x)+f(y).$$
It is a very well-known functional equation, which appears in various areas of ...
83
votes
5
answers
22k
views
Limit of the nested radical $x_{n+1} = \sqrt{c+x_n}$
(Fitzpatrick Advanced Calculus 2e, Sec. 2.4 #12)
For $c \gt 0$, consider the quadratic equation
$x^2 - x - c = 0, x > 0$.
Define the sequence $\{x_n\}$ recursively by fixing $|x_1| \lt c$ and then, ...
- 975
73
votes
18
answers
20k
views
Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1},$$
or, what is equivalent,
$$\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}.$$
What's ...
- 1,570
121
votes
3
answers
9k
views
Are all limits solvable without L'Hôpital Rule or Series Expansion
Is it always possible to find the limit of a function without using L'Hôpital Rule or Series Expansion?
For example,
$$\lim_{x\to0}\frac{\tan x-x}{x^3}$$
$$\lim_{x\to0}\frac{\sin x-x}{x^3}$$
$$\...
- 271k
44
votes
8
answers
23k
views
Why $\gcd(b,qb+r)=\gcd(b,r),\,$ so $\,\gcd(b,a) = \gcd(b,a\bmod b)$
Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so?
Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math....
- 1,641
167
votes
14
answers
43k
views
How to prove: if $a,b \in \mathbb N$, then $a^{1/b}$ is an integer or an irrational number?
It is well known that $\sqrt{2}$ is irrational, and by modifying the proof (replacing 'even' with 'divisible by $3$'), one can prove that $\sqrt{3}$ is irrational, as well. On the other hand, clearly ...
anonymous
448
votes
18
answers
61k
views
To sum $1+2+3+\cdots$ to $-\frac1{12}$
$$\sum_{n=1}^\infty\frac1{n^s}$$
only converges to $\zeta(s)$ if $\text{Re}(s)>1$.
Why should analytically continuing to $\zeta(-1)$ give the right answer?
perplexed
70
votes
2
answers
10k
views
Determinant of a rank $1$ update of a scalar matrix, or characteristic polynomial of a rank $1$ matrix
This question aims to create an "abstract duplicate" of numerous questions that ask about determinants of specific matrices (I may have missed a few):
Characteristic polynomial of a matrix ...
- 111k
131
votes
7
answers
81k
views
Values of $\sum_{n=0}^\infty x^n$ and $\sum_{n=0}^N x^n$
Why does the following hold:
\begin{equation*}
\displaystyle \sum\limits_{n=0}^{\infty} 0.7^n=\frac{1}{1-0.7} = 10/3\quad ?
\end{equation*}
Can we generalize the above to
$\displaystyle \sum_{n=...
189
votes
9
answers
62k
views
How to define a bijection between $(0,1)$ and $(0,1]$?
How to define a bijection between $(0,1)$ and $(0,1]$?
Or any other open and closed intervals?
If the intervals are both open like $(-1,2)\text{ and }(-5,4)$ I do a cheap trick (don't know if that'...
- 2,113
866
votes
23
answers
109k
views
369
votes
23
answers
47k
views
Zero to the zero power – is $0^0=1$?
Could someone provide me with a good explanation of why $0^0=1$?
My train of thought:
$x>0$
$0^x=0^{x-0}=0^x/0^0$, so
$0^0=0^x/0^x=\,?$
Possible answers:
$0^0\cdot0^x=1\cdot0^0$, so $0^0=1$
$0^0=0^...
- 3,941
109
votes
11
answers
9k
views
Closed form for $ \int_0^\infty {\frac{{{x^n}}}{{1 + {x^m}}}dx }$
I've been looking at
$$\int\limits_0^\infty {\frac{{{x^n}}}{{1 + {x^m}}}dx }$$
It seems that it always evaluates in terms of $\sin X$ and $\pi$, where $X$ is to be determined. For example:
$$\...
- 119k
67
votes
16
answers
50k
views
Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction
How can I prove that
$$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$
for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction.
Thanks
265
votes
32
answers
128k
views
Evaluating the integral $\int_0^\infty \frac{\sin x} x \,\mathrm dx = \frac \pi 2$?
A famous exercise which one encounters while doing Complex Analysis (Residue theory) is to prove that the given integral:
$$\int\limits_0^\infty \frac{\sin x} x \,\mathrm dx = \frac \pi 2$$
Well, can ...
user9413
348
votes
7
answers
48k
views
How can you prove that a function has no closed form integral?
In the past, I've come across statements along the lines of "function $f(x)$ has no closed form integral", which I assume means that there is no combination of the operations:
addition/...
- 5,431
136
votes
36
answers
297k
views
Proof that $1+2+3+4+\cdots+n = \frac{n\times(n+1)}2$
Why is $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$ $\space$ ?
- 1,535
130
votes
3
answers
126k
views
Expected time to roll all $1$ through $6$ on a die
What is the average number of times it would it take to roll a fair $6$-sided die and get all numbers on the die? The order in which the numbers appear does not matter.
I had this questions explained ...
- 1,465
210
votes
19
answers
144k
views
Evaluation of Gaussian integral $\int_{0}^{\infty} \mathrm{e}^{-x^2} dx$
How to prove
$$\int_{0}^{\infty} \mathrm{e}^{-x^2}\, dx = \frac{\sqrt \pi}{2}$$
- 7,768
11
votes
3
answers
2k
views
mod Distributive Law, factoring $\!\!\bmod\!\!:$ $\ ab\bmod ac = a(b\bmod c)$
I stumbled across this problem
Find $\,10^{\large 5^{102}}$ modulo $35$, i.e. the remainder left after it is divided by $35$
Beginning, we try to find a simplification for $10$ to get:
$$10 \equiv 3 ...
- 2,972
101
votes
15
answers
90k
views
How to prove that exponential grows faster than polynomial?
In other words, how to prove:
For all real constants $a$ and $b$ such that $a > 1$,
$$\lim_{n\to\infty}\frac{n^b}{a^n} = 0$$
I know the definition of limit but I feel that it's not enough to ...
- 6,877
72
votes
5
answers
56k
views
How to take the gradient of the quadratic form?
It's stated that the gradient of:
$$\frac{1}{2}x^TAx - b^Tx +c$$
is
$$\frac{1}{2}A^Tx + \frac{1}{2}Ax - b$$
How do you grind out this equation? Or specifically, how do you get from $x^TAx$ to $A^...
- 833
145
votes
32
answers
81k
views
Sum of First $n$ Squares Equals $\frac{n(n+1)(2n+1)}{6}$
I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:
$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$
I really ...
- 1,803
178
votes
17
answers
161k
views
How to prove Euler's formula: $e^{i\varphi}=\cos(\varphi) +i\sin(\varphi)$?
Could you provide a proof of Euler's formula: $e^{i\varphi}=\cos(\varphi) +i\sin(\varphi)$?
- 7,768
86
votes
15
answers
95k
views
Prove that $\lim \limits_{n \to \infty} \frac{x^n}{n!} = 0$, $x \in \Bbb R$.
Why is
$$\lim_{n \to \infty} \frac{2^n}{n!}=0\text{ ?}$$
Can we generalize it to any exponent $x \in \Bbb R$? This is to say, is
$$\lim_{n \to \infty} \frac{x^n}{n!}=0\text{ ?}$$
This is being ...
- 1,205
151
votes
2
answers
46k
views
Examples of bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$
Could any one give an example of a bijective map from $\mathbb{R}^3\rightarrow \mathbb{R}$?
Thank you.
- 34.8k
50
votes
3
answers
58k
views
Explain why $E(X) = \int_0^\infty (1-F_X (t)) \, dt$ for every nonnegative random variable $X$
Let $X$ be a non-negative random variable and $F_{X}$ the corresponding CDF. Show,
$$E(X) = \int_0^\infty (1-F_X (t)) \, dt$$
when $X$ has : a) a discrete distribution, b) a continuous ...
- 1,411
2
votes
3
answers
2k
views
Solving linear congruence (modular inverse or fraction) via gcd Bezout equation
Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this ...
- 2,955
257
votes
9
answers
32k
views
Evaluating $\lim\limits_{n\to\infty} e^{-n} \sum\limits_{k=0}^{n} \frac{n^k}{k!}$
I'm supposed to calculate:
$$\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$$
By using WolframAlpha, I might guess that the limit is $\frac{1}{2}$, which is a pretty interesting and nice ...
- 43.7k
130
votes
24
answers
27k
views
In classical logic, why is $(p\Rightarrow q)$ True if both $p$ and $q$ are False?
I am studying entailment in classical first-order logic.
The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is:
$$\begin{array}{|c|c|c|}
\...
- 1,419
6
votes
4
answers
10k
views
Prove that $(ma, mb) = |m|(a, b)\ $ [GCD & LCM Distributive Law]
I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$.
My thoughts:
If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max + ...
- 189
45
votes
8
answers
23k
views
Why is $a^n - b^n$ divisible by $a-b$?
I did some mathematical induction problems on divisibility
$9^n$ $-$ $2^n$ is divisible by 7.
$4^n$ $-$ $1$ is divisible by 3.
$9^n$ $-$ $4^n$ is divisible by 5.
Can these be generalized as
$a^n$ $-$...
- 557
30
votes
1
answer
4k
views
Discrete logarithm tables for the fields $\Bbb{F}_8$ and $\Bbb{F}_{16}$.
The smallest non-trivial finite field of characteristic two is
$$
\Bbb{F}_4=\{0,1,\beta,\beta+1=\beta^2\},
$$
where $\beta$ and $\beta+1$ are primitive cubic roots of unity, and zeros of the
...
178
votes
2
answers
106k
views
Discontinuous derivative. [duplicate]
Could someone give an example of a ‘very’ discontinuous derivative? I myself can only come up with examples where the derivative is discontinuous at only one point. I am assuming the function is real-...
- 1,897