# Questions tagged [number-theory]

Questions on advanced topics - beyond those in typical introductory courses: higher degree algebraic number and function fields, Diophantine equations, geometry of numbers / lattices, quadratic forms, discontinuous groups and and automorphic forms, Diophantine approximation, transcendental numbers, elliptic curves and arithmetic algebra geometry, exponential and character sums, Zeta and L-functions, multiplicative and additive number theory, etc.

4,905 questions
Filter by
Sorted by
Tagged with
36k 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 ...
19k 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 ...
19k 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$?
6k views

### If $a \mid m$ and $(a + 1) \mid m$, prove $a(a + 1) | m$.

Can anyone help me out here? Can't seem to find the right rules of divisibility to show this: If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.
34k 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$ ...
179k 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. ...
318 views

### Solving linear congruence (modular inverse or fraction) by solving Bezout equation

Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this ...
2k views

### Show that $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n d^{n-1},a-b)$

How to show that $$\gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b )$$ $a,b\in \mathbb Z$ where $d=\gcd(a,b)$? Note $\$ Some of the answers below were merged from this ...
10k views

### Is the Euler phi function bounded below?

I am working on a question for my number theory class that asks: Prove that for every integer $n \geq 1$, $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$. However, I was searching around Google, and on ...
20k views

### Split $n$ into nontrivial factors via a nontrivial square-root of $1\!\pmod{\!n}$

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...
5k views

13k views

### Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
23k views

### prove that $\frac{(2n)!}{(n!)^2}$ is even if $n$ is a positive integer

Prove that $\frac{(2n)!}{(n!)^2}$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the ...
1k views

### Proving $p\nmid \binom{p^rm}{p^r}$ where $p\nmid m$

A question from Advanced Modern Algebra by Joseph J.Rotman. Let $n=(p^r)m$ such that the prime $p\nmid m$.Prove that $p\nmid \dbinom{n}{p^r}$.HINT: Assume otherwise, cross multiply and apply ...
704 views

### Curves triangular numbers.

Sometimes you have to deal with this equation: $X^2+aX+Y^2+bY=Z^2+cZ$ $a,b,c$ - integer coefficients. I wrote below - to start a particular solution of Diophantine equations. To do this, use the ...
10k views

### Is there possibly a largest prime number?

Prime numbers are numbers with no factors other than one and itself. Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of "...
17k views

2k views

### Find all solutions to $x^2\equiv 1\pmod {91},\ 91 = 7\cdot 13$

I split this into $x^2\equiv 1\pmod {7}$ and $x^2\equiv 1\pmod {13}$. For $x^2\equiv 1\pmod {7}$, i did: $$(\pm1 )^2\equiv 1\pmod{7}$$ $$(\pm2 )^2\equiv 4\pmod{7}$$ $$(\pm3 )^2\equiv 2\pmod{7}$$ ...
51k views

### Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
6k views

### $n!+1$ being a perfect square

One observes that \begin{equation*} 4!+1 =25=5^{2},~5!+1=121=11^{2} \end{equation*} is a perfect square. Similarly for $n=7$ also we see that $n!+1$ is a perfect square. So one can ask the truth of ...
6k views

### Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

This question relates to a discussion on another message board. Euclid's proof of the infinitude of primes is an indirect proof (a.k.a. proof by contradiction, reductio ad absurdum, modus tollens). My ...
99k 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)
8k views

### Why doesn't $0$ being a prime ideal in $\mathbb Z$ imply that $0$ is a prime number?

I know that $1$ is not a prime number because $1\cdot\mathbb Z=\mathbb Z$ is, by convention, not a prime ideal in the ring $\mathbb Z$. However, since $\mathbb Z$ is a domain, $0\cdot\mathbb Z=0$ is ...
35k views

### Continued fraction of a square root

If I want to find the continued fraction of $\sqrt{n}$ how do I know which number to use for $a_0$? Is there a way to do it without using a calculator or anything like that? What's the general ...
801 views

I input ...
1k views

### ${\gcd(n,m)\over n}{n\choose m}$ is an integer

Prove that for every $n\geq m \geq1$ natural numbers, the following number is an integer: $${\gcd(n,m)\over n}\cdot{n\choose m}$$ Where $\gcd$ is the greatest common divisor. I tried to make it ...
900 views

### Parametrization of solutions of diophantine equation

The issue I discussed in this thread. Parametrization of solutions of diophantine equation $x^2 + y^2 = z^2 + w^2$ Generally speaking at the forum often ask a question about this equation. So I ...