Skip to main content

Questions tagged [elementary-number-theory]

For questions on introductory topics in number theory, such as divisibility, prime numbers, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, quadratic number fields, Pell's equations, and related topics.

4,890 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
37 votes
0 answers
856 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 ...
Vepir's user avatar
  • 12.5k
37 votes
0 answers
652 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 ...
Ahmad's user avatar
  • 712
33 votes
0 answers
1k views

For any fixed integer $ a \gt 1 $, how do you prove that $\frac{a^p-1}{a-1}$ is not always prime given prime $ p \not \mid a-1$?

I assumed this would be easy to prove but it turned out to be quite hard since the go to methods don't work on this problem. Once we fix any $a\gt 1$, we need an algorithm to produce a prime $p$ that ...
arbashn's user avatar
  • 685
29 votes
0 answers
1k views

Are there unique solutions for $n=\sum_\limits{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 ...
draks ...'s user avatar
  • 18.5k
27 votes
0 answers
1k 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 ...
Glinka's user avatar
  • 3,202
23 votes
0 answers
616 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}...
SomeStrangeUser's user avatar
22 votes
0 answers
997 views

What is the last non-zero digit of $(\dots((2018\underset{! \text{ occurs }1009\text{ times}}{\underbrace{!)!)!\dots)!}}$?

Without using computer programs, can we find the last non-zero digit of $$(\dots((2018\underset{! \text{ appears }1009\text{ times}}{\underbrace{!)!)!\dots)!}}?$$ What I know is that the last non-zero ...
Hussain-Alqatari's user avatar
21 votes
0 answers
4k 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 ...
ShBh's user avatar
  • 6,114
21 votes
0 answers
1k 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 ...
Larry Freeman's user avatar
20 votes
0 answers
288 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 ...
Yuriy S's user avatar
  • 31.6k
19 votes
0 answers
292 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\}$...
Vepir's user avatar
  • 12.5k
19 votes
0 answers
510 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 ...
Mastrem's user avatar
  • 8,431
19 votes
0 answers
459 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 ...
Peter's user avatar
  • 84.9k
18 votes
0 answers
217 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,...
Nilotpal Sinha's user avatar
18 votes
0 answers
325 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 ...
Vladislav Kharlamov's user avatar
18 votes
0 answers
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 $...
Asimov's user avatar
  • 3,034
17 votes
0 answers
252 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 ...
Aritro Pathak's user avatar
15 votes
0 answers
287 views

When the sum of the first $n$ consecutive even ($2k \gt 0$) powers is a prime number?

When $n=2$, we know 4 Fermat primes (among the 5 which are known) satisfying this condition: $$ 1^2+2^2 =5$$ $$ 1^4+2^4 =17$$ $$ 1^8+2^8 = 257$$ $$ 1^{16}+2^{16} = 65537.$$ One may wonder for what ...
René Gy's user avatar
  • 3,716
15 votes
0 answers
200 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=\{...
user160886's user avatar
15 votes
0 answers
441 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 ...
Yuriy S's user avatar
  • 31.6k
15 votes
0 answers
253 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 ...
goblin GONE's user avatar
15 votes
0 answers
722 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 ...
Elaqqad's user avatar
  • 13.8k
14 votes
0 answers
317 views

Is $2p-2$ a period of $\{a_n\}$ modulo a prime $p$?

Let ${a_0}=1$, ${a_n}=\sum_{k=0}^{n-1} \binom{2n}{2k}a_ka_{n-k-1}$ for $n>0$. That is, ${a_n}=$ A002067(n) in OEIS. Question: for any prime $p$, is $2p-2$ a period of $\{a_n\}$ modulo $p$? And it ...
Jinyuan's user avatar
  • 240
14 votes
0 answers
368 views

Do prime of the form $4k+1$ ever lead the greatest prime factor race?

Note: Posted in MO since it is unanswered in MSE. Analogous to Chebyshev's race between primes, I examined the race between primes in the greatest prime factors, GPF, of natural numbers. Similar to ...
Nilotpal Sinha's user avatar
14 votes
0 answers
202 views

Does there exist any $p >0$ such that $\frac{1}{n^p \sin(n)} \to 0 \;,n\to+\infty$?

Does there exist any $p >0$ such that \begin{equation*} \frac{1}{n^p \sin(n)} \to 0 \;,n\to+\infty \;? \end{equation*} If there is one, what's the infimum of those $p$? Is it also a minimum? I ...
Bob's user avatar
  • 5,783
14 votes
0 answers
466 views

Looking for all sequences such that $a_i^2+a_j^2=a_k^2+a_l^2$ whenever $i^2+j^2=k^2+l^2$

I'm working in a difficult functional equation, and I have reduced the problem to the following question ($\mathbb{N}$ denotes the set of non negative integers $0,1,2,3,4\cdots$) Question: Can we ...
Elaqqad's user avatar
  • 13.8k
14 votes
0 answers
380 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)=\...
Steven Stadnicki's user avatar
13 votes
0 answers
189 views

Can the sequence $\{\lfloor \alpha n \rfloor\}$ be divided into two parts with equal sums, for all $\alpha \in \mathbb{R}$?

Define the sequence $a_n = \lfloor \alpha n \rfloor$ for a real number $\alpha$. Is there any pair of natural numbers $k, l$ satisfying the following condition?: $$\sum_{n=1}^k a_n = \sum_{n=k+1}^l ...
dodicta's user avatar
  • 1,451
13 votes
0 answers
305 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 ...
Larry Freeman's user avatar
13 votes
0 answers
188 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) : ...
Peter's user avatar
  • 84.9k
13 votes
0 answers
602 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 ...
ketchupcoke's user avatar
  • 1,139
13 votes
0 answers
357 views

Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$ ...
Tony Reix's user avatar
  • 393
12 votes
0 answers
285 views

Are there any $3$-Fermat-pseudoprimes of the form $k^4+1$?

Suppose $k$ is a positive integer and $N:=k^4+1$ is composite. Can $N$ be a $3$-Fermat-pseudoprime; that is, can the congruence $$3^{N-1}\equiv 1 \mod{N}$$ hold ? I checked up to $k=10^8$ and found ...
Peter's user avatar
  • 84.9k
12 votes
0 answers
166 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=...
Peter's user avatar
  • 84.9k
12 votes
0 answers
474 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)$, ...
Mike's user avatar
  • 1,312
12 votes
1 answer
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 ...
user avatar
12 votes
0 answers
2k 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 ...
ajay's user avatar
  • 1,165
12 votes
1 answer
772 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$...
Ghartal's user avatar
  • 4,368
12 votes
1 answer
349 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 ...
Zander's user avatar
  • 10.9k
11 votes
0 answers
111 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 \...
Peter's user avatar
  • 84.9k
11 votes
0 answers
206 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–...
user759001's user avatar
11 votes
1 answer
521 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 ...
Pedja's user avatar
  • 12.9k
11 votes
0 answers
346 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 ...
Larry Freeman's user avatar
11 votes
0 answers
204 views

A non-zero continuous function such that summing over equally spaced values always gives zero

A long time ago now, I wondered whether or not there exists some sequence of real numbers $(a_n)_{n \in \mathbb{N}}$, different from the zero sequence, such that for any $m \in \mathbb{N}$, $$ \sum_{n=...
Mike Daas's user avatar
  • 1,879
11 votes
0 answers
550 views

Finite algebraic structures where all hyperoperations (addition, multiplication, exponentiation, tetration, etc.) are well-defined

Let $\langle R, +, \times, \uparrow, \uparrow\uparrow, \uparrow\uparrow\uparrow, \ldots; 0, 1\rangle$ be an algebraic structure with two constants $0, 1$ and where an infinite sequence of binary ...
pregunton's user avatar
  • 5,831
11 votes
0 answers
314 views

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

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 ...
Jeppe Stig Nielsen's user avatar
11 votes
0 answers
285 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 ...
Kieren MacMillan's user avatar
11 votes
0 answers
220 views

Prime factors of $\sum_{k=1}^{30}k^{k^k}$

I checked the prime factors of $$\sum_{k=1}^{30}k^{k^k}$$ and did not find any upto $10^8$ Are there any useful restrictions to accelerate the search ?
Peter's user avatar
  • 84.9k
11 votes
0 answers
625 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 ...
Bruno Joyal's user avatar
11 votes
1 answer
197 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 $\...
k1.M's user avatar
  • 5,466

1
2 3 4 5
98