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.

Filter by
Sorted by
Tagged with
152
votes
12answers
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 ...
136
votes
3answers
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 ...
85
votes
6answers
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$?
29
votes
4answers
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$.
208
votes
10answers
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$ ...
658
votes
13answers
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. ...
1
vote
2answers
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 ...
12
votes
5answers
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 ...
21
votes
4answers
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 ...
28
votes
5answers
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 ...
33
votes
5answers
5k views

Can $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m$ are perfect squares?

Can the expression $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m \in \mathbb{N}$ are perfect squares? It doesn't seem likely, the only way that could happen is if for example $\sqrt{m} = a-\sqrt{n}...
5
votes
3answers
625 views

Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$

Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$ for $p\neq q$ distinct primes. Where can I start with this proof? It looks similar to the Chinese Remainder Theorem, ...
2
votes
3answers
684 views

Prime factor of $A=14^7+14^2+1$ [closed]

Find a prime factor of $A=14^7+14^2+1$. Obviously without just computing it.
40
votes
1answer
3k views

How does $ \sum_{p<x} p^{-s} $ grow asymptotically for $ \text{Re}(s) < 1 $?

Note the $ p < x $ in the sum stands for all primes less than $ x $. I know that for $ s=1 $, $$ \sum_{p<x} \frac{1}{p} \sim \ln \ln x , $$ and for $ \mathrm{Re}(s) > 1 $, the partial sums ...
5
votes
4answers
5k views

Solutions to $ax^2 + by^2 = cz^2$

The integer solutions to the equation $x^2 + y^2 = z^2$ are very well studied. I'm wondering if there's any literature about the integer solutions to the equation $ax^2 + by^2 = cz^2$ where a,b,c are ...
1
vote
4answers
260 views

How to solve a linear congruence $8n+9\equiv 0\pmod{\!1163}$

Problem : Solve in $\mathbb N$ : $8n+9\equiv 0\pmod{1163}$ The mathematics give me : $n=435+1163k$ , $k\in\mathbb N$ $1163$ is a prime number $8n\equiv -9\pmod{1163}$ $8n\equiv 1154\pmod{...
35
votes
6answers
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 ...
35
votes
7answers
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 ...
5
votes
3answers
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 ...
1
vote
4answers
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 ...
35
votes
10answers
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 "...
24
votes
3answers
17k views

If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The proof is already given in the textbook but I tried other way around. Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,...
13
votes
3answers
6k views

Does the sum of reciprocals of primes converge?

Is this series known to converge, and if so, what does it converge to (if known)? Where $p_n$ is prime number $n$, and $p_1 = 2$, $$\sum\limits_{n=1}^\infty \frac{1}{p_n}$$
3
votes
1answer
610 views

Deriving Chinese Remainder Theorem from gcd Bezout identity

We want to find the solution $x$ to the congruence system $$\begin{align} x &\equiv r_1 \!\!\!\pmod{\!m_1}\\ x &\equiv r_2 \!\!\!\pmod{\!m_2}\end{align},\ \ {\rm where}\ \ \gcd(m_1, m_2) = 1$...
42
votes
3answers
8k views

How do I count the subsets of a set whose number of elements is divisible by 3? 4?

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that $\displaystyle \sum_{k=0}^{n} {n \...
50
votes
6answers
11k views

Do harmonic numbers have a “closed-form” expression?

One of the joys of high-school mathematics is summing a complicated series to get a “closed-form” expression. And of course many of us have tried summing the harmonic series $H_n =\sum \limits_{k \leq ...
14
votes
2answers
16k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
15
votes
2answers
3k views

Fermat numbers are coprime

So today in my final for number theory I had to prove that the Fermat numbers ($F_n=2^{2^n}+1$) are coprime. I know that the standard proof uses the following: $F_n=F_1\cdots F_{n-1}+2$ and then the ...
103
votes
23answers
20k 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 ...
25
votes
4answers
12k views

When is $\sin(x)$ rational?

Obviously, there are some points (e.g. $\pi$, $30^\circ$) but I am unsure if there are more. How can it be proved that there are no more points, or, if there are, what those points will be? EDIT: I ...
82
votes
6answers
29k 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 ...
39
votes
7answers
57k views

In how many ways can a number be expressed as a sum of consecutive numbers? [duplicate]

All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example $9$ can be expressed in three such ways, $2+3+4$, $4+5$ or simply $9$. In how many ...
12
votes
4answers
3k views

Erdős-Straus conjecture

The Erdős-Straus Conjecture (ESC), states that for every natural number $n \geq 2$, there exists a set of natural numbers $a, b, c$ , such that the following equation is satisfied: $$\frac{4}{n}=\...
20
votes
2answers
23k views

The units of $\mathbb Z[\sqrt{2}]$

How can I show that the units $u$ of $R=\mathbb Z[\sqrt{2}]$ with $u>1$ are $(1+ \sqrt{2})^{n}$ ? I have proved that the right ones are units because their module is one, and it is said to me to ...
5
votes
7answers
1k views

Solving a homogeneous quadratic equation in three variables over the integers.

Is there any procedure for determining if an infinite amount of solutions exist for an equation of the type $x^2 = ay^2 + byz + cz^2$ for arbitrary integer constants $a, b, c$ and variables $x, y, z \...
4
votes
3answers
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}$$ ...
66
votes
4answers
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?
51
votes
3answers
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 ...
25
votes
5answers
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 ...
192
votes
30answers
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)
42
votes
3answers
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 ...
33
votes
5answers
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 ...
6
votes
2answers
801 views

How does Mathematica solve $f(x)\equiv 0\pmod p$?

I input ...
16
votes
2answers
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 ...
2
votes
1answer
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 ...
98
votes
3answers
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
22
votes
2answers
7k views

A conjecture about numbers of the form $10^{m}(2^{k}−1)+2^{k-1}−1$, where $m$ is the number of decimal digits of $ 2^{k-1}$.

Question Numbers $n$ of the form $10^{m}(2^{k}−1)+2^{k-1}−1$, where $m$ is the number of decimal digits of $ 2^{k-1}$. For example: $k=1$ then $n=10$. $k=2$ then $n=31$. $k=3$ then $n=...
17
votes
5answers
2k views

Integral solutions of $x^2+y^2+1=z^2$

I am interested in integral solutions of $$x^2+y^2+1=z^2.$$ Is there a complete theory comparable to the one for $x^2+y^2=z^2?$
17
votes
3answers
16k views

Number of integer solutions of $x^2 + y^2 = k$

I'm looking for some help disproving an answer provided on a StackOverflow question I posted about computing the number of double square combinations for a given integer. The original question is ...
9
votes
3answers
1k views

Group theory proof of existence of a solution to $x^2\equiv -1\pmod p$ iff $p\equiv 1 \pmod 4$

I've read through the elementary proof of why there exists a solution $x$ to $x^2\equiv -1\pmod p$ iff $p\equiv 1 \pmod 4$ for $p$ an odd prime. Is there a group theory generalization for this fact as ...

1
2 3 4 5
99