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
Filter by
Sorted by
Tagged with
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 \...

1
2 3 4 5
80