# Questions tagged [elementary-number-theory]

Questions on congruences, linear Diophantine equations, greatest common divisor, divisibility, etc.

3,321 questions
1k views

926 views

### Are there unique solutions for $n=\sum_{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 (...
514 views

### Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
358 views

### Proving there is no non-abelian finite simple group of order a Fibonacci number

"Prove there does not exist a finite simple non-abelian group of order of a Fibonacci number" I would like to answer the above question, but I currently have few ideas of where to begin. I ...
289 views

234 views

### Why is counting the number of least prime factors of a sequence of consecutive integers insufficient to resolve Legendre's Conjecture?

I've been thinking a long time about Legendre's Conjecture. A few nights ago, I came across the following argument which is of course too simple to be true. I would greatly appreciate if someone ...
293 views

### Proving $2+2^2/2+2^3/3+2^4/4+\cdots=0$ elementarily

In the first chapter of Gouvea's intro to $p$-adics, there's a heuristic argument that $$\frac{2}{1}+\frac{2^2}{2}+\frac{2^3}{3}+\frac{2^4}{4}+\cdots=0 \tag{\ast}$$ as $2$-adic numbers, since it'...
541 views

I am investigating a modified version of the sieve of Eratosthenes, where instead of eliminating numbers starting with $n$ by adding $n$ each time, which results in the set of primes, $n+m$ is added ...
444 views

### when $F_n^2+F_m^2$ is a square for fibonacci numbers

This is a curiosity question I'm trying to solve a Diophantine equation and I need some results about fibonnacci numbers, I encountered this problem: For which couple of integers $(n,m)$ the ...
344 views

261 views

### If $b$ is even and not a power of two, can $b^4+1$ be a weak pseudoprime?

The complete question is already in the title but we shall provide some motivation as well. We study generalized Fermat numbers defined by: $$\mathrm{GF}(n,b) = b^{2^n}+1$$ where $b$ and $n$ are ...
434 views

### Olympiad-style question about functions satisfying condition $f(f(f(n))) = f(n+1) + 1$

QN: What functions (from non-negative integers to non-negative integers) satisfy the condition $$f(f(f(n))) = f(n+1) + 1$$ Comment: Evidently $f(n) = n+ 1$ is one solution. Equally evidently no ...
345 views

### Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
436 views

### What is stopping every Mordell equation from having a [truly] elementary proof?

The Mordell equation is the Diophantine equation $$Y^2 = X^3-k \tag{1}$$ where $k$ is a given integer. There is no known single method — elementary or otherwise — to solve equation $(1)$ for all $k$, ...
795 views

### IMO 1979 problem

The question is $$\text{If }\, p, \ q\in \mathbb{N}, \;1-\frac12+\frac13-\frac14-\dotsb-\frac{1}{1318}+\frac{1}{1319}=\frac{p}{q}.\qquad \text{Prove that } 1979\mid p.$$ So my solution went like this:...
1k views

### Prove that Bezout's coefficients given by the extended Euclidean algorithm are minimal in absolute value

Bezout's lemma states that if a and b are integers, and at least one of them is non-zero, then there exist integers $x, y$ such that $$ax + by = gcd(a, b)$$ One way of finding such a pair $(x, y)$ is ...
213 views

117 views

216 views

### The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
201 views

### Looking for the most elementary proof that $48X^4+12X^2+1=Y^2$ has no non-trivial integer solution.

As relayed in this question of mine (which is more general in scope), I believe I have found a relatively easy, and completely elementary, way to show that the equation $$48X^4 + 12X^2+1 = Y^2$$ has ...
I had been researching over the Extended Euclidean Algorithm when I happened to observe that the Bézout Coefficients were always relatively prime. Let $a$ and $b$ be two integers and $d$ their GCD. ...
### Is $2^9$ the only power of two that is the sum of two odd perfect powers?
Let $m\ge 1$ be an integer. For which $m$ can we find odd perfect powers $a,b$ with $a+b=2^m$ ? The only solution, I found for $m\le 80$ is $m=9$ with the representation $$2^9=13^2+7^3$$ The ...