Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.
11
votes
4answers
1k views
If $a | m$ and $(a + 1) | 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 | m$ and $(a + 1) | m$, then $a(a + 1) | m$.
18
votes
9answers
3k views
$\sqrt a$ is either an integer or an irrational number.
I got this interesting question in my mind:
How do we prove that if $a \in \mathbb N$, then $\sqrt a$ is an integer or an irrational number?
Can we extend this result? That is, can it be shown ...
48
votes
5answers
3k 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$ ...
28
votes
5answers
2k 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$?
19
votes
7answers
2k views
How can you prove that the square root of two is irrational?
I have read a few proofs that $\sqrt{2}$ is irrational.
I have never, however, been able to really grasp what they were talking about.
Is there a simplified proof that $\sqrt{2}$ is irrational?
22
votes
1answer
670 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 ...
11
votes
4answers
4k views
Simple explanation and examples of the Miller-Rabin Primality Test
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 ...
21
votes
1answer
1k views
Alternative proof that $(a^2+b^2)/(ab+1)$ is a square when it's an integer
Let $a,b$ be positive integers.
When $$k = \frac{a^2 + b^2}{ab+1}$$ is an integer, it is a square.
Proof 1: (Ngô Bảo Châu): Rearrange to get $a^2-akb+b^2-k=0$, as a quadratic in $a$ this has two ...
5
votes
2answers
3k 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 ...
17
votes
9answers
3k 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 ...
47
votes
24answers
10k views
Best book ever on Number Theory
Which is the single best book for Number Theory that everyone who loves Mathematics should read?
12
votes
4answers
1k 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 ...
5
votes
2answers
1k views
$\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ [duplicate]
Possible Duplicate:
Number theory proving question?
Dear friends,
Since $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1, how can we prove that
$$
\gcd (b ^ x - 1, b ^ y - 1, b ^ ...
6
votes
4answers
2k views
Modular exponentiation using Euler’s theorem
How can I calculate $27^{41}\ \mathrm{mod}\ 77$ as simple as possible?
I already know that $27^{60}\ \mathrm{mod}\ 77 = 1$ because of Euler’s theorem:
$$ a^{\phi(n)}\ \mathrm{mod}\ n = 1 $$
and
$$ ...
4
votes
5answers
842 views
calculating $a^b \!\mod c$
What is the fastest way (general method) to calculate the quantity $a^b \!\mod c$? For example $a=2205$, $b=23$, $c=4891$.
