0
votes
2answers
63 views

Proof that doesn't exists a rational $s$ such that $s^2 = 6$

Well, I solved it, and I would like to know if there is anything that can be corrected or improved here. I think that the proof ended up too long, and with too many letters. Surely there is a better ...
5
votes
7answers
232 views

Alternative Proof of Infinitely Many Primes? [duplicate]

I've seen Euclid's proof of infinitely many primes, what are other approaches to proving there are infinitely many primes?
1
vote
1answer
35 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} = ...
10
votes
1answer
106 views

Seeking a more direct proof for: $m+n\mid f(m)+f(n)\implies m-n\mid f(m)-f(n)$

If $f:\mathbb N\to\mathbb Z$ satisfies: $$\forall n,m\in\mathbb N\,, n+m\mid f(n)+f(m)$$ How to show that this implies: $$\forall n,m\in\mathbb N,\,n-m\mid f(n)-f(m)?$$ I was almost incidentally ...
0
votes
5answers
178 views

Prove that $4^n$ is not divisible by 3.

How can one prove that $4^n$ is not divisible by 3, for any $n \ge 0$? One way I found is to proof that $4^n - 1$ is always divisible by 3 (as demonstrated in a question here), thus $4^n$ could ...
2
votes
2answers
114 views

Solve $ax \equiv b \mod m$ without Linear Congruence Theorem or Euclid's Algorithm?

Origin page 5. The overhead doesn't look like Linear Congruence Theorem or anything from Euclid's Algorithm. page 4 tries to delineate ...
1
vote
2answers
67 views

Is there an elementary proof that $n \mid \phi(p^n-1)$?

When I teach finite fields, one fun corollary is that $n \mid \phi(p^n-1)$, where $\phi$ is the Euler-phi function and $p$ is prime. I spent several minutes in my office after class one day looking ...
2
votes
1answer
34 views

Solving a divisibility problem using group theory

Inspired by this I decided to show this: Let $P_n=\displaystyle\prod_{1\leq i<j\leq n} \big(x_i-x_j\big)$ where $x_1\,\dots\, x_n$ are arbitrary integers. Prove $n!\,\big|\, 2P_n$. I am ...
3
votes
2answers
71 views

Observations needed to justify an algebraic passage in proof of a property of $\varphi$ (Totient function)

Let $\varphi$ be the Euler's totient function and let $n\in \mathbb{N}$ be factorized in primes as $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_l^{\alpha_l}$. I was looking for alternative methods to ...
16
votes
2answers
794 views

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

Can someone prove 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 good proofs, but ...
2
votes
1answer
81 views

How to show that $\lfloor n/1\rfloor+\lfloor n/2 \rfloor+…+\lfloor n/n\rfloor+\lfloor{\sqrt{n}}\rfloor$ is even?

Let $n$ is a natural number. Prove that $$\left\lfloor\frac{n}{1}\right\rfloor+\left\lfloor\frac{n}{2}\right\rfloor+....+\left\lfloor\frac{n}{n}\right\rfloor+\left\lfloor{\sqrt{n}}\right\rfloor$$ ...
3
votes
1answer
132 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 ...
4
votes
1answer
84 views

Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$. This seems like it should be a simple question, but try as I might, I can't seems to find any way that does ...
2
votes
1answer
111 views

Proof Without Words for $GCD(a,b) \cdot LCM(a,b)=ab$

Is there any proof without words for the identity $GCD (a,b) \cdot LCM(a,b)=ab$ ?
1
vote
0answers
39 views

Ineqality regarding LCM of $1, 2, \ldots, n$

While going through F. Beukers proof of irrationality of $\zeta(3)$ I found the inequality $d_{n} < 3^{n}$ for all sufficiently large values of $n$ where $d_{n}$ denotes the LCM of all the numbers ...
5
votes
1answer
207 views

Dividing Squares Fails to Invoke Contradiction: Two Elementary Divisibility Proofs

$x^2 \text{ is even } \iff x \text{ is even } \tag{Thm 3.12, P76}$ $\text{ Let } x, y \in \mathbb{Z}. \text{ Then } x \;\& \; y \text{ are of the same parity } \iff x + y \text{ is even.} \tag{Thm ...
0
votes
2answers
147 views

Prove $\log_a(b)$ is irrational given that $a, b$ are positive distinct primes.

I know this is a classical proof by contradiction exercise, and there are full solutions else where, doing a quick search I didn't find any, but I would approach this question like this: Suppose ...
1
vote
1answer
53 views

If $p$ is irreducible and $p \not \mid a$, then $\text{gcd}(p,a)=\pm 1$.

I will be taking a Rings and Fields course in the Fall, so I figured I would read ahead in the textbook (A First Course in Abstract Algebra, by Anderson and Feil) to prepare. Recall the following ...
4
votes
3answers
297 views

Why are only fractions with denominator 2 and 5 non-repeating?

Given a rational number $\frac{n}{d}$, I understand that in the base $10$ number system, the number can be represented as a non-repeating decimal number if and only if $d$ has only prime factors of ...
6
votes
1answer
156 views

Combinatorial proof of the fact $p$ doesn't divide $ n \choose p^k$

Let $p^k | n$ and $p^{k+1} \nmid n$. Is there any combinatorial proof of the fact that $p \nmid {n \choose p^{k}} $ ?
2
votes
5answers
121 views

$x^2\mid27 \implies x\mid9$ : Prove

$x$ is given as a natural number. I was trying this by direct proof: assume $27\mid x^2$, then $x^2 = 27m \Longrightarrow x=3\cdot \sqrt{3m} \Longrightarrow \sqrt{3m}$ must be integer ...
3
votes
0answers
258 views

Proof that $ 1^3+2^3+\cdots +n^3 = (1+2+\cdots+n)^2$ without using induction [duplicate]

Possible Duplicate: Intuitive explanation for the identity $\sum\limits_{k=1}^n {k^3} = \left(\sum\limits_{k=1}^n k\right)^2$ How to prove this without using mathematical induction? ...
3
votes
3answers
148 views

If $n\equiv 2\pmod 3$, then $7\mid 2^n+3$.

In this (btw, nice) answer to Twin primes of form $2^n+3$ and $2^n+5$, it was said that: If $n\equiv 2\pmod 3$, then $7\mid 2^n+3$? I'm not familiar with these kind of calculations, so I'd like ...