All Questions
Tagged with elementary-number-theory summation
108
questions
44
votes
2
answers
207k
views
How to get to the formula for the sum of squares of first n numbers? [duplicate]
Possible Duplicate:
How do I come up with a function to count a pyramid of apples?
Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?
Finite Sum of Power?
I know that the sum of ...
- 1,588
35
votes
8
answers
7k
views
Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?
If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically ...
- 2,077
16
votes
4
answers
17k
views
Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$
This question is from [Number Theory George E. Andrews 1-1 #3].
Prove that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$$
This problem is driving me crazy.
$$x^n-y^n = (x-y)(x^{n-1}+...
- 777
5
votes
1
answer
2k
views
Legendre symbol: Showing that $\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0$
I have a question about Legendre symbol.
Let $a$, $b$ be integers. Let $p$ be a prime not dividing $a$. Show that the Legendre symbol verifies:
$$\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0.$$
I ...
- 686
4
votes
3
answers
4k
views
How to prove $\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$
For every positive integer $d$, we let $\tau\left(d\right)$ be the number of positive divisors of $d$.
Prove that
\begin{align}
\sum_{d|n} \tau^3(d)
= \left(\sum_{d|n} \tau (d)\right)^2
\end{align}
...
- 2,879
50
votes
4
answers
5k
views
Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$
Let $\varphi(n)$ be Euler's totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$.
Challenge: Prove
$$\sum_{k=1}^n \left\lfloor \frac{n}{k} \right\...
- 55.8k
15
votes
4
answers
57k
views
Sum of odd numbers always gives a perfect square. [duplicate]
$1 + 3 = 4$ (or $2$ squared)
$1+3+5 = 9$ (or $3$ squared)
$1+3+5+7 = 16$ (or $4$ squared)
$1+3+5+7+9 = 25$ (or $5$ squared)
$1+3+5+7+9+11 = 36$ (or $6$ squared)
you can go on like this as far as you ...
- 197
8
votes
3
answers
1k
views
Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$
Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$;
I was stuck with this question for a while... Help me please!!! Thanks!!!
- 151
4
votes
3
answers
243
views
Prove $z^n + 1/{z^n}$ is rational if $z+1/z$ is rational
Knowing that $z + \frac{1}{z} = 3$ ($z \in \mathbb{R}$), prove that $z^n + \frac{1}{z^n} \in \mathbb{Q}$ ($n \in \mathbb{N}$ and $n \geq 1$).
I've tried to find a general formula for $z^n + \frac{1}{...
- 2,833
4
votes
4
answers
246
views
Find $x$ such that $\sum_{k=1}^{2014} k^k \equiv x \pmod {10}$
Find $x$ such that $$\sum_{k=1}^{2014} k^k \equiv x \pmod {10}$$
I knew the answer was $3$.
- 2,977
17
votes
1
answer
10k
views
Sum of GCD(k,n)
I want to find this
$$ \sum_{k=1}^n \gcd(k,n)$$
but I don't know how to solve. Does anybody can help me to finding this problem.
Thanks.
- 333
10
votes
5
answers
16k
views
Show $\sum\limits_{d|n}\phi(d) = n$. [duplicate]
Show $\sum\limits_{d|n}\phi(d) = n$.
Example : $\sum\limits_{d|4}\phi(d) = \phi(1) + \phi(2) + \phi(4) = 1 + 1 + 2 = 4$
I was told this has a simple proof. Problem is, I can not think of a way to ...
- 249
3
votes
0
answers
2k
views
$ 1^k+2^k+3^k+...+(p-1)^k $ always a multiple of $p$? [closed]
I would appreciate if somebody could help me with the following problem:
Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is
$$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
- 5,506
29
votes
0
answers
1k
views
Are there unique solutions for $n=\sum_\limits{j=1}^{g(k)} a_j^k$?
Edward Waring, asks whether for every natural number $n$ there exists an associated positive
integer s such that every natural number is the sum of at most $s$ $k$th powers of natural
numbers (for ...
- 18.6k
6
votes
2
answers
8k
views
Show that $\sum\nolimits_{d|n} \frac{1}{d} = \frac{\sigma (n)}{n}$ for every positive integer $n$.
Show that $\sum\nolimits_{d|n} \frac{1}{d} = \frac{\sigma (n)}{n}$ for every positive integer $n$.
where $\sigma (n)$ is the sum of all the divisors of $n$
and $\sum\nolimits_{d|n} f(d)$ is the ...
- 3,188