Questions tagged [elementary-number-theory]
Questions on divisibility, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, and other related topics in the early study of number theory. More advanced topics should receive the number-theory tag instead.
3,993
questions with no upvoted or accepted answers
74
votes
0answers
2k 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^{\...
33
votes
1answer
727 views
Given a positive integer $t$ does there always exist a natural number $k$ such that $(k!)^2$ is a factor of $(2k-t)!$?
For all natural numbers $k$ the ratio
$$
\frac{(2k)!}{(k!)^2}=\binom{2k}k
$$
is an integer. From staring at the Pascal triangle long and hard, we know that these ratios grow rather quickly as $k$ ...
31
votes
0answers
547 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$,...
24
votes
0answers
417 views
Grasshopper jumping on circles
Can we characterize the grasshopper sequence?
Let $n\in\mathbb N$ be the number of stones $s\in\{0,1,2\dots,n-1\}=S$ on a circle that the grasshopper can jump on. Let $v(s)$ be the number of times ...
24
votes
0answers
406 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 ...
24
votes
0answers
1k 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 (for ...
23
votes
0answers
652 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 ...
18
votes
0answers
467 views
Explaining a pattern observed when computing $\binom{2n}{n}$
While looking at various ways of computing $\binom{2n}{n}$ for various values of $n$, I tried the following method: First, define the sequence $T_0=\{n+1,...,2n\}$, then for $k=1,...,n$, given $T_{k-1}...
18
votes
1answer
520 views
$\lfloor x^n\rfloor\lfloor y^n\rfloor$ is a perfect square
Let $x,y\ge 1$ be non-integer real numbers such that $\lfloor x^n\rfloor\lfloor y^n\rfloor$ is a perfect square for all natural numbers $n$. Does it follow that $x=y$?
From this question we know the ...
17
votes
0answers
228 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 ...
16
votes
0answers
367 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 ...
16
votes
0answers
969 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 ...
14
votes
0answers
397 views
Fibonacci-like sequences mod $p$ where $a_{n+1}$ only really depends on $a_n$.
Consider a prime $p$ and a sequence $(a_n)_{n\ge 0}$ in $\mathbb{F}_p$ satisfying $a_{n+2}=a_{n+1}+a_n$ for all $n\ge 0$.
Now, assume that each element of the sequence only really depends on the ...
14
votes
0answers
167 views
Rare gaps between integers having the same number of co-primes
Let $\varphi(x)$ be the Euler totient function. For $k = 1,2,3,\ldots$ I calculated the number of solutions of $\varphi(x) = \varphi(x+k)$. I observed that we have very few solutions when $k = 3,9,15,...
14
votes
0answers
176 views
For what $n$ can $\{1, 2,\ldots, n\}$ be partitioned into equal-sized sets $A$, $B$ such that $\sum_{k\in A}k^p=\sum_{k\in B}k^p$ for $p=1, 2, 3$?
This is a recent problem in American Mathematical Monthly. The deadline for this question just passed:
$\textbf{Problem:}$ For which positive integers $n$ can $\{1,2,3,...,n\}$ be partitioned into ...
14
votes
0answers
555 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 ...
14
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 $...
13
votes
0answers
209 views
Are $3^6-6^3$ and $4^8-8^4$ the only sums of four $a^b-b^a,1\lt a\lt b$ numbers?
Question
How many numbers of form $a_0^{b_0}-b_0^{a_0}$ are a "nontrivial" sum of four such numbers $a_i^{b_i}-b_i^{a_i}$ ?
The "nontrivial" means: all unordered pairs $\{a_i,b_i\}$...
13
votes
1answer
484 views
Elementary proof for infinitude of primes in an arithmetic progression of a special form
In this recent question the asker was looking for a proof of the existence of infinitely many prime numbers $p$ such that both $p-2$ and $p+2$ are composite. A highly upvoted answer by Ege Erdil made ...
13
votes
0answers
157 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) :
...
13
votes
0answers
288 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
182 views
A Combinatorial problem involving $\mathbf{Z}/2^k\mathbf{Z}$
Let $k$ be a positive integer. Let $A=\{a_1,\dots, 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=\{...
13
votes
0answers
364 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
205 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 ...
12
votes
0answers
276 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
138 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=...
12
votes
0answers
580 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
358 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)=\...
12
votes
1answer
599 views
Power Diophantine equation involving primes: $(p+q)^q-p^q-q^q+1=n^{p-q}$
Suppose $p$ and $q$ are prime numbers, and $n>1$ is a positive integer. Find all solutions to the following Diophantine equation:$$(p+q)^q-p^q-q^q+1=n^{p-q}$$
What I have tried:
Obviously $p>q$...
12
votes
1answer
315 views
Can $p^{q-1}\equiv 1 \pmod {q^3}$ for primes $p<q$?
For prime $q$ can it be that
$$
p^{q-1}\equiv 1 \pmod{q^k}
$$
for some prime $p<q$ and for $k\ge 3$?
There doesn't seem to be a case with $k=3$ and $q<90000$, and I also checked for small ...
11
votes
0answers
312 views
Does the equation $\sigma(\sigma(x^2))=2x\sigma(x)$ have any odd solutions?
(Note: This question has been cross-posted to MO.)
Let $\sigma(x)$ denote the classical sum of divisors of the positive integer $x$.
Here is my question:
Does the equation $\sigma(\sigma(x^2))=2x\...
11
votes
1answer
499 views
A non-composite sequences
Can you provide a counterexample for a claim given below?
Inspired by Puzzle 937 I have formulated the following claim:
For any $n > 0$ let $B = p_1 \cdot p_2 \cdot .... \cdot p_n$ be the ...
11
votes
0answers
289 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 ...
11
votes
0answers
362 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
75 views
Is $n^2\mid \sigma(n)^{\sigma(n)}-1$ possible for $n>1$?
Inspired by Martin Hopf I used another number theoretical function for this question.
If $\sigma(n)$ is the divisor-sum function ($1$ and $n$ are included, $\sigma(1)=1$) , can we have $$n^ 2\mid \...
10
votes
0answers
974 views
In Search Of Elementary Proof Of Kobayashi's Theorem
There is a theorem in Number Theory due to Hiroshi Kobayashi (possibly less famous). The statement of this theorem is quite simple-looking. The original proof of Kobayashi relies on Siegel's Theorem ...
10
votes
1answer
79 views
A topology over $\Bbb N$ based on convergence of series.
Define $\tau=\{U\subseteq \Bbb N:U\in\{\Bbb N,\emptyset\}\vee\sum_{n\notin U}n^{-1}<\infty\}$. In other words, a subset of $\Bbb N$ is closed iff it is $\Bbb N$ or the sum of the inverses of its ...
10
votes
0answers
285 views
Prove $\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$ for $p$ being an odd prime
I need to prove the following:
$$\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$$
...with $p$ being an odd prime number. The statement is obviously true for$\pmod p$ because left-...
10
votes
1answer
344 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-\...
10
votes
0answers
216 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
336 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
1answer
592 views
Generalisation of prime numbers to matrices?
Is it possible to generalise prime numbers to matrices? I'm trying to solve a Rubix cube in the minimum number of steps and I think this would be useful. I think it's possible to represent Rubix cube ...
10
votes
1answer
3k views
Vertices of a cyclic polygon have integer coordinates and sides. If odd $n$ divides the squares of the sides, it divides twice the area.
IMO 2016 Problem 3:
Let $P = A_1 A_2 \cdots A_k$ be a convex polygon in the plane. The vertices $A_1, A_2, \ldots, A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An ...
10
votes
0answers
279 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
369 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
348 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 ...
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 ...
10
votes
1answer
160 views
If all the numbers $(1^\alpha,\,2^\alpha,\,3^\alpha,\,\dotsc)$ are integer, then $\alpha$ is an integer.
A theorem of Siegel asserts that
If $\beta>0$ and $2^\beta,\,3^\beta,\,5^\beta$ are integers, then $\beta$ is an integer.
The following result is a beautiful consequence of this theorem
If $\...
9
votes
0answers
162 views
A generalization of Feit–Thompson conjecture, for square-free integers
Few weeks ago I wondered about if the following conjecture is in the literature or well if it is possible to find a counterexample. I evoke a generalization of a well-known conjecture, I mean the Feit–...
9
votes
0answers
227 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 \...
