4
votes
0answers
113 views

Will this algorithm stop before time?

For every $n \in \mathbb N$, let's define $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{if it never appeared before} \\ a_{i+1} = 2a_i \pmod {2^n},& ...
1
vote
1answer
39 views

Prove that $\dfrac{\sigma_1(n)}{n} = \sigma_{-1}(n)$ where $\sigma_x(n)$ is the sum of the $x$th powers of the positive divisors of $n$.

I computed $\dfrac{\sigma_1(n)}{n}$ and $\sigma_{-1}(n)$ on a good hundred values of $n$, and they seem to always match. For example: $\dfrac{\sigma_1(6)}{6} = \dfrac{1 + 2 + 3 + 6}{6} = ...
3
votes
1answer
113 views

A Shorter Proof of Rosser's Theorem Without Using The Prime Number Theorem

While researching on the elementary proof of Bertrand's Postulate I came to know about a theorem of Rosser's which states that $p_n$ $>$ $n$ $\text{ln}$ $n$. I have seen Rosser's original proof and ...
-1
votes
1answer
88 views

Prove $p$$_n$$_+$$_1$ $<$ $2p_n$ without using the Bertrand's Postulate [closed]

Recently I have been researching on the Bertrand's Postulate to find and elementary proof of it. I have been able to prove that (if I have not made a very pathetic mistake) for any composite $n$ ...
2
votes
0answers
52 views

Alternative Proof for “Roots of Mertens Function-Farey Sequence-Cosines Relations”

You can write Merten's function as $$ M(n)= \sum_{a\in \mathcal{F}_n} e^{2\pi i a} , $$ where $\mathcal{F}_n$ is the Farey sequence of order $n$. The sum may be split into imaginary and real ...
1
vote
2answers
47 views

Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof. So, I ...
16
votes
2answers
892 views

Prove that $x^3 + y^3 = z^3$ has no integer solutions as simply as possible

Can someone provide the proof of the special case of Fermat's Last Theorem for $n=3$, i.e., that $$ x^3 + y^3 = z^3, $$ has no positive integer solutions, as simply as possible? I have seen some ...
3
votes
1answer
169 views

An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
1
vote
2answers
61 views

Showing that $\{ n\mid \nu(n) \equiv 0 \pmod e\}$ is independent of primitive root

Let us suppose we have a prime $p > 3$ and two primitive roots $g_1, g_2$ of $p$ with index functions $\nu_1$ and $\nu_2$ (so that $g_1^{\nu_1(n)} = n$). Also suppose that $ef = p-1$ is a ...
15
votes
1answer
1k views

A proof of Wolstenholme's theorem

This was inspired by this question. I tried to use the identity $${2n \choose n}=\sum_{k=0}^n {n \choose k}^2$$ (see this question) to prove that $$\binom{2p}p\equiv2\pmod{p^3}$$ if $p\gt3$ is ...
3
votes
3answers
821 views

$p=4n+3$ never has a Decomposition into $2$ Squares, right?

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma. Is it correct to say that, primes of the form $p=4n+3$, never have ...
1
vote
3answers
289 views

How to prove $e$ isn't a $\frac {a}{b}$. Not irrationality with other ways or about transcendental, only about fractions

I would like a proof that $e$ isn't a fraction $\frac{a}{b}$, for $a,b \in Z$ and $mdc(a,b)=1$. Just a observation =) I'd like a proof with fractions, not about $e$ irrationality or if $e$ is ...
3
votes
1answer
299 views

Is this a good proof of Wilson's theorem? — ($(n-1)!+1 \equiv_n 0$ iff n is prime)

Theorem: $(n - 1)! + 1 \equiv_n 0$ if and only if $n$ is prime. To prove that if $n$ is not prime this is not true is trivial, so I'm just interested in proving that this is true for all p: ...
32
votes
1answer
2k views

$n!$ is never a perfect square if $n\geq2$. Is there a proof of this that doesn't use Chebyshev's theorem?

If $n\geq2$, then $n!$ is not a perfect square. The proof of this follows easily from Chebyshev's theorem, which states that for any positive integer $n$ there exists a prime strictly between $n$ and ...
17
votes
4answers
1k views

Proofs that every natural number is a sum of four squares.

I am planning to write a little note detailing several proofs of Lagrange's theorem that every natural number can be written as the sum of four perfect squares. I know of three different proofs so ...