The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [number-theory]

Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

Filter by
Sorted by
Tagged with
682
votes
43answers
100k views

Different methods to compute $\sum\limits_{k=1}^\infty \frac{1}{k^2}$ (Basel problem)

As I have heard people did not trust Euler when he first discovered the formula (solution of the Basel problem) $$\zeta(2)=\sum_{k=1}^\infty \frac{1}{k^2}=\frac{\pi^2}{6}.$$ However, Euler was Euler ...
608
votes
13answers
163k views

Does Pi contain all possible number combinations?

I came across the following image: Which states: $\pi$ Pi Pi is an infinite, nonrepeating $($sic$)$ decimal - meaning that every possible number combination exists somewhere in pi. ...
260
votes
11answers
26k views

Is '$10$' a magical number or I am missing something?

It's a hilarious witty joke that points out how every base is '$10$' in its base. Like, 2 = 10 (base 2) 8 = 10 (base 8) My question is if whoever invented the ...
213
votes
8answers
64k views

What is the importance of the Collatz conjecture?

I have been fascinated by the Collatz problem since I first heard about it in high school. Take any natural number $n$. If $n$ is even, divide it by $2$ to get $n / 2$, if $n$ is odd multiply it by ...
186
votes
10answers
29k views

Is there an elementary proof that $\sum \limits_{k=1}^n \frac1k$ is never an integer?

If $n>1$ is an integer, then $\sum \limits_{k=1}^n \frac1k$ is not an integer. If you know Bertrand's Postulate, then you know there must be a prime $p$ between $n/2$ and $n$, so $\frac 1p$ ...
184
votes
30answers
93k views

Books on Number Theory for Layman [closed]

Books on Number Theory for anyone who loves Mathematics?(Beginner to Advanced & just for someone who has a basic grasp of math)
183
votes
2answers
11k views

How to show $e^{e^{e^{79}}}$ is not an integer

In this question, I needed to assume in my answer that $e^{e^{e^{79}}}$ is not an integer. Is there some standard result in number theory that applies to situations like this? After several years, ...
179
votes
1answer
22k views

Are 14 and 21 the only “interesting” numbers?

The numbers 14 and 21 are quite interesting. The prime factorisation of 14 is $2\cdot 7$ and the prime factorisation of $14+1$ is $3\cdot 5$. Note that 3 is the prime after 2 and 5 is the prime ...
160
votes
1answer
8k views

A variation of Fermat's little theorem in the form $a^{n-d}\equiv a$ (mod $p$).

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
152
votes
3answers
14k views

Is 2048 the highest power of 2 with all even digits (base ten)?

I have a friend who turned 32 recently. She has an obsessive compulsive disdain for odd numbers, so I pointed out that being 32 was pretty good since not only is it even, it also has no odd factors. ...
147
votes
2answers
14k views

Proof that ${\left(\pi^\pi\right)}^{\pi^\pi}$ (and now $\pi^{\left(\pi^{\pi^\pi}\right)}$ is a noninteger

Conor McBride asks for a fast proof that $$x = {\left(\pi^\pi\right)}^{\pi^\pi}$$ is not an integer. It would be sufficient to calculate a very rough approximation, to a precision of less than 1, and ...
144
votes
12answers
33k views

How to prove: if $a,b \in \mathbb N$, then $a^{1/b}$ is an integer or an irrational number?

It is well known that $\sqrt{2}$ is irrational, and by modifying the proof (replacing 'even' with 'divisible by $3$'), one can prove that $\sqrt{3}$ is irrational, as well. On the other hand, clearly ...
143
votes
10answers
8k views

How far can one get in analysis without leaving $\mathbb{Q}$?

Suppose you're trying to teach analysis to a stubborn algebraist who refuses to acknowledge the existence of any characteristic $0$ field other than $\mathbb{Q}$. How ugly are things going to get for ...
135
votes
1answer
4k views

Pythagorean triples that “survive” Euler's totient function

Suppose you have three positive integers $a, b, c$ that form a Pythagorean triple: \begin{equation} a^2 + b^2 = c^2. \tag{1}\label{1} \end{equation} Additionally, suppose that when you apply Euler's ...
133
votes
6answers
6k views

Do Arithmetic Mean and Geometric Mean of Prime Numbers converge?

I was looking at a list of primes. I noticed that $ \frac{AM (p_1, p_2, \ldots, p_n)}{p_n}$ seemed to converge. This led me to try $ \frac{GM (p_1, p_2, \ldots, p_n)}{p_n}$ which also seemed to ...
129
votes
3answers
16k views

The square roots of different primes are linearly independent over the field of rationals

I need to find a way of proving that the square roots of a finite set of different primes are linearly independent over the field of rationals. I've tried to solve the problem using elementary ...
119
votes
2answers
6k views

Is there any mathematical reason for this “digit-repetition-show”?

The number $$\sqrt{308642}$$ has a crazy decimal representation : $$555.5555777777773333333511111102222222719999970133335210666544640008\cdots $$ Is there any mathematical reason for so many ...
119
votes
1answer
21k views

Can $x^{x^{x^x}}$ be a rational number?

If $x$ is a positive rational number, but not an integer, then can $x^{x^{x^x}}$ be a rational number ? We can prove that if $x$ is a positive rational number but not an integer, then $x^x$ can not ...
114
votes
15answers
11k views

Infiniteness of non-twin primes.

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are ...
112
votes
1answer
2k views

Gross-Zagier formulae outside of number theory

(Edit: I have asked this question on MO.) The Gross-Zagier formula and various variations of it form the starting point in most of the existing results towards the Birch and Swinnerton-Dyer ...
110
votes
1answer
3k views

Is There An Injective Cubic Polynomial $\mathbb Z^2 \rightarrow \mathbb Z$?

Earlier, I was curious about whether a polynomial mapping $\mathbb Z^2\rightarrow\mathbb Z$ could be injective, and if so, what the minimum degree of such a polynomial could be. I've managed to ...
104
votes
5answers
9k views

A multiplication algorithm found in a book by Paul Erdős: how does it work?

I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"): We can ...
103
votes
3answers
4k views

Least prime of the form $38^n+31$

I search the least n such that $$38^n+31$$ is prime. I checked the $n$ upto $3000$ and found none, so the least prime of that form must have more than $4000$ digits. I am content with a probable ...
103
votes
1answer
5k views

$n!$ is never a perfect square if $n\geq2$. Is there a proof of this that doesn't use Chebyshev's theorem?

If $n\geq2$, then $n!$ is not a perfect square. The proof of this follows easily from Chebyshev's theorem, which states that for any positive integer $n$ there exists a prime strictly between $n$ and $...
102
votes
1answer
3k views

Find all functions $f$ such that if $a+b$ is a square, then $f(a)+f(b)$ is a square

Question: For any $a,b\in \mathbb{N}^{+}$, if $a+b$ is a square number, then $f(a)+f(b)$ is also a square number. Find all such functions. My try: It is clear that the function $$f(x)=x$$ ...
99
votes
5answers
7k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
97
votes
1answer
3k views

All polynomials with no natural roots and integer coefficients such that $\phi(n)|\phi(P(n))$

Let $P(x)$ be a polynomial with integer coefficients such that the equation $P(x)=0$ has no positive integer solutions. Find all polynomials $P(x)$ such that for all positive integers $n$ we have $\...
94
votes
22answers
18k views

Different ways to prove there are infinitely many primes?

This is just a curiosity. I have come across multiple proofs of the fact that there are infinitely many primes, some of them were quite trivial, but some others were really, really fancy. I'll show ...
93
votes
7answers
10k views

How can adding an infinite number of rationals yield an irrational number?

For example how come $\zeta(2)=\sum_{n=1}^{\infty}n^{-2}=\frac{\pi^2}{6}$. It seems counter intuitive that you can add numbers in $\mathbb{Q}$ and get an irrational number.
91
votes
4answers
5k views

Complexity class of comparison of power towers

Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
90
votes
4answers
2k views

A real number $x$ such that $x^n$ and $(x+1)^n$ are rational is itself rational

Let $x$ be a real number and let $n$ be a positive integer. It is known that both $x^n$ and $(x+1)^n$ are rational. Prove that $x$ is rational. What I have tried: Denote $x^n=r$ and $(x+1)^n=s$ ...
86
votes
5answers
12k views

Is it possible to represent every huge number in abbreviated form?

Consider the following expression. $1631310734315390891207403279946696528907777175176794464896666909137684785971138$ $2649033004075188224$ This is a $98$ decimal digit number. This can be ...
85
votes
3answers
121k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
84
votes
1answer
3k views

Numbers $n$ such that the digit sum of $n^2$ is a square

Let $S(n)$ be the digit sum of $n\in\mathbb N$ in the decimal system. About a month ago, a friend of mine taught me the following: $$S\left(9\color{red}{^2}\right)=S(81)=8+1=3\color{red}{^2}$$ $$S\...
83
votes
2answers
2k views

Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers?

Our algebra teacher usually gives us a paper of $20-30$ questions for our homework. But each week, he tells us to do all the questions which their number is on a specific form. For example, last ...
83
votes
4answers
3k views

How to solve these two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I cannot progress anymore. ...
83
votes
0answers
1k views

Does every ring of integers sit inside a ring of integers that has a power basis?

Given a finite extension of the rationals, $K$, we know that $K=\mathbb{Q}[\alpha]$ by the primitive element theorem, so every $x \in K$ has the form $$x = a_0 + a_1 \alpha + \cdots + a_n \alpha^n,$$ ...
78
votes
6answers
13k views

$x^y = y^x$ for integers $x$ and $y$

We know that $2^4 = 4^2$ and $(-2)^{-4} = (-4)^{-2}$. Is there another pair of integers $x, y$ ($x\neq y$) which satisfies the equality $x^y = y^x$?
78
votes
2answers
26k views

Why is it hard to prove whether $\pi+e$ is an irrational number?

From this list I came to know that it is hard to conclude $\pi+e$ is an irrational? Can somebody discuss with reference "Why this is hard ?" Is it still an open problem ? If yes it will be helpful ...
77
votes
6answers
24k views

Is the notorious $n^2 + n + 41$ prime generator the last of its type?

The polynomial $n^2+n+41$ famously takes prime values for all $0\le n\lt 40$. I have read that this is closely related to the fact that 163 is a Heegner number, although I don't understand the ...
76
votes
9answers
10k views

The myth of no prime formula?

Terence Tao claims: For instance, we have an exact formula for the $n^\text{th}$ square number – it is $n^2$ – but we do not have a (useful) exact formula for the $n^\text{th}$ ...
74
votes
3answers
3k views

Mathematicians shocked(?) to find pattern in prime numbers

There is an interesting recent article "Mathematicians shocked to find pattern in "random" prime numbers" in New Scientist. (Don't you love math titles in the popular press? Compare to the source ...
74
votes
1answer
5k views

Direct proof that $\pi$ is not constructible

Is there a direct proof that $\pi$ is not constructible, that is, that squaring the circle cannot be done by rule and compass? Of course, $\pi$ is not constructible because it is transcendental and ...
71
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, $...
69
votes
2answers
2k views

Representing every positive rational number in the form of $(a^n+b^n)/(c^n+d^n)$

About a month ago, I got the following : For every positive rational number $r$, there exists a set of four positive integers $(a,b,c,d)$ such that $$r=\frac{a^\color{red}{3}+b^\color{red}{3}}{...
68
votes
7answers
15k views

Can someone please explain the Riemann Hypothesis to me… in English?

I've read so much about it but none of it makes a lot of sense. Also, what's so unsolvable about it?
65
votes
5answers
10k views

What is so interesting about the zeroes of the Riemann $\zeta$ function?

The Riemann $\zeta$ function plays a significant role in number theory and is defined by $$\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} \qquad \text{ for } \sigma > 1 \text{ and } s= \sigma + it$$ ...
65
votes
2answers
3k views

Is this similarity to the Fourier transform of the von Mangoldt function real?

Mathematica knows that the logarithm of $n$ is: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ The von Mangoldt function should then be: $$\Lambda(n)=\...
64
votes
1answer
3k views

Does Fermat's Last Theorem hold for cyclotomic integers in $\mathbb{Q(\zeta_{37})}$?

The first irregular prime is 37. Does FLT(37) $$x^{37} + y^{37} = z^{37}$$ have any solutions in the ring of integers of $\mathbb Q(\zeta_{37})$, where $\zeta_{37}$ is a primitive 37th root of unity?...
63
votes
18answers
8k views

Is there a simple function that generates the series; $1,1,2,1,1,2,1,1,2…$ or $-1,-1,1,-1,-1,1…$ [closed]

I'm thinking about this question in the sense that we often have a term $(-1)^n$ for an integer $n$, so that we get a sequence $1,-1,1,-1...$ but I'm trying to find an expression that only gives every ...