Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-number-theory]

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

63
votes
0answers
1k views

$\frac{1}{n}$ as a difference of Egyptian fractions with all denominators $<n$

Is there a good characterization of the set $S$ of positive integers $n$ such that $\frac{1}{n}$ can be represented as a difference of Egyptian fractions with all denominators $< n$? For example, $...
41
votes
0answers
1k views

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
21
votes
0answers
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 (...
20
votes
0answers
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 ...
19
votes
0answers
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 ...
19
votes
0answers
289 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$, ...
16
votes
0answers
196 views

The famous prime race and generalizations

So I was messing around with the famous prime race that comes down to this: We make a list of primes. The list has two rows; the top row is for primes $1\mod 4$ and the bottom row for primes $3\mod 4$...
15
votes
0answers
181 views

Is every finite list of integers coprime to $n$ congruent $\pmod n$ to a list of consecutive primes?

For example the list $(2, 1, 2, 1)$ is congruent $\pmod 3$ to the consecutive primes $(5, 7, 11, 13)$. But how about the list $(1,1,1,1,1,1,1,1,2,3,4,3,2,3,1) \mod 5$? More generally, we are given ...
15
votes
0answers
904 views

Understanding Ramanujan's approach in his proof of Bertrand's Postulate

I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$ What would be wrong with this approach for ...
13
votes
0answers
239 views

Number as the sum of digits of some degree

We will say that the measure of a number is equal to the maximum degree in which it is possible to represent a number in the form of a sum of digits copied (You can not rearrange the numbers). For ...
13
votes
0answers
151 views

Surprising continued fractions of numbers in the form $\sum_{n=0}^\infty \frac{1}{a^{2^n}}$, including the same pattern for every $a>2$

I've been interested in the numbers of this form because it can be proved that for integer $a \geq 2$ all of them are irrational: $$x_a=\sum_{n=0}^\infty \frac{1}{a^{2^n}}$$ They satisfy the ...
13
votes
0answers
294 views

Greedy algorithm Egyptian fractions for irrational numbers - patterns and irrationality proofs

This is related to another question on this site, but it's not a duplicate, because the actual questions I ask are completely different. In one of the answers Jeffrey Shallit provided a very useful ...
13
votes
0answers
1k views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor $...
12
votes
0answers
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 ...
12
votes
0answers
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'...
12
votes
0answers
541 views

What is known about this sequence?

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 ...
12
votes
0answers
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 ...
12
votes
0answers
344 views

An infinitude of “congruence condition” primes?

Background: Several special classes of primes can be written as primes that satisfy some additional constraint $f(p)\equiv 0\pmod p$; for instance, Wilson primes are congruence primes with $f(p)=\...
11
votes
0answers
161 views

Is there a finite list of identites in the language of $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm})$ that generates all the others?

Let $\Phi$ denote the set of all identities satisfied by $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm}).$ Question. Is $\Phi$ finitely axiomatizable? If so, I'd like to see a list of ...
11
votes
0answers
185 views

Which digit occurs most often?

Is there any method to calculate, which digit occurs most often in the number $$4 \uparrow \uparrow \uparrow \uparrow 4\ ,$$ the fourth Ackermann-number ? Or would it be necessary to calculate the ...
10
votes
0answers
233 views

Is there an elementary argument for $\prod\limits_{p \le n}p < 3^n$ where $p$ is prime.

I was reading Hanson's proof that $\prod\limits_{p^a \le n}p^a < 3^n$ where $p$ is a prime and it occurred to me that there might be a simpler argument for $\prod\limits_{p \le n} p < 3^n$. Am ...
10
votes
0answers
110 views

Are there infinite many solutions of $\ \ |\varphi(n+1)-\varphi(n)|=2\ \ $?

The solutions of the equation $$|\varphi(n+1)-\varphi(n)|=2$$ upto $\ \ n=10^8-1\ \ $ are (the first entries of the arrays) : ...
10
votes
0answers
189 views

$\gcd(p_{n-1}, \ n^5 - n^3 + n^2 - n + 1) = 1$ where $p_n = n$th prime.

How can I prove in general that, for all $n\geq 2$: $$ \gcd(p_{n-1}, \ n^5 - n^3 + n^2 - n + 1) = 1 $$ Seems to always be true: ...
10
votes
0answers
307 views

Let $|A|=|B|=|C|=n$ be three finite sets of integers. Find $\min |\{ab+c \mid a \in A, b \in B, c \in C\}|$.

For a triple of sets of integers $A,B,C$ with $|A|=|B|=|C|=n$, we can compute the set $S_{A,B,C} = \{ab+c \mid a \in A, b \in B, c \in C\}$. I am interested in the minimum sized $S_{A,B,C}$ when ...
10
votes
0answers
296 views

Pythagorean triples and Pell numbers.

This problem is mentioned in this one, but I think it deserves some attention on its own. So here it is: For any integers $n,m > 0$: If $2mn(n+m)(n-m)$ divides $(n^2 + m^2 + 1)(n^2 + m^2 - 1)$, ...
10
votes
0answers
179 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all $...
10
votes
0answers
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 ...
10
votes
0answers
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 ...
10
votes
0answers
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 ...
10
votes
0answers
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$, ...
10
votes
0answers
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:...
10
votes
0answers
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 ...
9
votes
0answers
213 views

Number of ways a natural number can be written as a sum of naturals that are all coprime to it.

let $X: \mathbb{N}^2 \to \mathbb{N}$ Let $X(a ,b)$ be the number of unique ways we can write $a$ as the sum of $b$ many numbers, where each of the $b$ numbers are co-prime to $a$. Where $a$ $\in \...
9
votes
0answers
283 views

A conjecture regarding odd perfect numbers

(Note: This question has now been cross-posted to MO.) Let $\sigma(z)$ denote the sum of the divisors of $z \in \mathbb{N}$, the set of positive integers. Denote the deficiency of $z$ by $D(z):=2z-\...
9
votes
0answers
117 views

Can a prime have arbitary many representations as a sum of two perfect powers?

Let $p$ be a prime number and $f(p)$ be the number of representations $$p=a+b$$ with perfect powers $0<a< b$ For example, $13$ has the only representation $$4+9=13$$ hence $f(13)=1$ $$41=9+32=...
9
votes
0answers
150 views

products of factorials

Let $F = \{n! \mid n > 1\}$. Let $S_1$ be the set of integers which can be expressed as a product of one or more (not necessarily distinct) elements of $F$. Let $S_2$ be the set of integers which ...
9
votes
0answers
128 views

When Does $\sigma(q^k)$ Have a Prime Factor Greater Than $q$

Let $q$ be prime and $k$ be a natural number. When does $\sigma(q^k)$ have a prime factor greater than $q$? We can slightly reduce the problem by noting that $$\sigma(q^k)=\frac{q^{k+1}-1}{q-1}$$ ...
9
votes
0answers
153 views

A Combinatorial problem involving $\mathbf{Z}/2^k\mathbf{Z}$

Let $k$ be a positive integer. Let $A=\{a_1,\cdots, a_{2^k}\}$ be a subset of $\mathbf{Z}/2^{k+1}\mathbf{Z}$ whose image in $\mathbf{Z}/2^k\mathbf{Z}$ is the whole $\mathbf{Z}/2^k\mathbf{Z}$. Let $B=\{...
9
votes
0answers
450 views

An interesting problem which only needs elementary number theory

A problem about elementary number theory While writing my paper, I came across the following problem: (all the discussion assume that $q$ is prime and $\alpha $ is a positive integer. ) We first ...
9
votes
0answers
231 views

Olympic number theory problem: is this solution fine and sufficiently well written?

Determine all positive integers $m$ such that the ratios $$ \frac{2(5^m+5)}{3^m+1}\quad\text{and}\quad \frac{9^m+1}{5^m+5}$$ are both integers. Attempt at a solution: If the ratios are both ...
9
votes
0answers
250 views

What is the Gauss sum equivalent of $\Gamma(s+1) = s\Gamma(s)$?

Gauss sums are analogous to the Gamma function: fix a complex number $s$ with real part $>0$. Then we have a multiplicative character $\chi_s :\mathbf R^{\times}_{>0} \to \mathbf C^\times$ given ...
8
votes
0answers
117 views

Odd numbers with $\varphi(n)/n < 1/2$

The topic was also discussed in this MathOverflow question. From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
8
votes
0answers
179 views

How to prove that below quantity is purely imaginary?

How do I prove that the following quantity is purely imaginary: $$\sum_{0\leq l_1<l_2<l_3<l_4\leq q-1} e^{-2\pi i \frac{(l_1^2-l_2^2+l_3^2-l_4^2)}{q} } $$ where $q$ is an odd number?
8
votes
0answers
108 views

Did Lagrange and/or Lebesgue and/or Lucas solve Ljunggren's equation?

Ljunggren’s Diophantine equation is $$X^2+1=2Y^4.$$ In 1942, he solved it using extremely difficult means; Mordell asked for a simpler proof, so people have been trying (unsuccessfully) ever since. ...
8
votes
0answers
127 views

There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$.

I observed that if $n$ is a composite number of the form $6k + 1$ then there are at least three divisors of $n - 1$ which do not divide $\phi(n)$ (Euler's totient function). Is this true in general? ...
8
votes
0answers
267 views

Is a finite number of quadratic equations in two variables sufficient to solve for the two variables?

Let's say I’m trying to solve a Diophantine problem in two positive integers, $y$ and $q$. Furthermore, let’s say I can derive an extremely large (read: arbitrary) number of equations of the form $$ay^...
8
votes
0answers
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 ...
8
votes
0answers
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 ...
8
votes
0answers
669 views

proof - Bézout Coefficients are always relatively prime

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. ...
7
votes
0answers
148 views

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 ...