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 ...
137k 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