Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.
12
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$.
20
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$?
20
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
675 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 ...
23
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?
13
votes
4answers
2k 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 ...
7
votes
4answers
2k views
Undergraduate/High-School-Olympiad Level Introductory Number Theory Books For Self-Learning
I don't know whether the books metioned in Best ever book on Number Theory are beyond undergraduate/high-school-olympiad level.
Please recommend your favourite.
23
votes
2answers
853 views
Proof that a natural number multiplied by some integer results in a number with only one and zero as digits
I recently solved a problem, which says that,
a positive integer can be multiplied with another integer resulting in
a positive integer that is composed only of one and zero as digits.
How can ...
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
934 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$.
25
votes
4answers
3k views
Nice proofs of $\zeta(4) = \pi^4/90$?
I know some nice ways to prove that $\zeta(2) = \sum_{n=1}^{\infty} \frac{1}{n^2} = \pi^2/6$. For example, see Robin Chapman's list or the answers to the question "Different methods to compute ...
1
vote
1answer
450 views
If the order divides a prime P then the order is P (or 1)
I've just come up with this question as I'm studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it's known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. ...
7
votes
1answer
367 views
If $\gcd(a,b)=d$, then $\gcd(ac,bc)=cd$?
$A$ an integral domain, $a,b,c\in A$. If $d$ is a greatest common divisor of $a$ and $b$, is it true that $cd$ is a greatest common divisor of $ca$ and $cb$? I know it is true if $A$ is a UFD, but ...
7
votes
3answers
510 views
When do the multiples of two primes span all large enough natural numbers?
It is well-known that given two primes $p$ and $q$, $pZ + qZ = Z$ where $Z$ stands for all integers.
It seems to me that the set of natural number multiples, i.e. $pN + qN$ also span all natural ...
2
votes
0answers
112 views
The homomorphism defined by the system of genus characters
Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$.
We say $D = b^2 - 4ac$ is the discriminant of $F$.
It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$).
If ...
5
votes
2answers
654 views
Proof of a formula involving Euler's totient function.
The third formula on the wikipedia page for the Totient function states that $$\varphi (mn) = \varphi (m) \varphi (n) \cdot \dfrac{d}{\varphi (d)} $$
where $d = \gcd(m,n)$.
How is this claim ...
32
votes
8answers
2k views
Is zero odd or even?
Some books say even numbers start from two but if you consider the number line concept, I think zero should be even because it is in between -1 and +1 (i.e in between 2 odd numbers). What is the real ...
14
votes
3answers
931 views
Why doesn't 0 being a prime ideal in 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\}$ ...
9
votes
2answers
1k views
Three variable, third degree Diophantine equation
I haven't found any useful method to solve the following problem: Prove that if $x,y,z\in\mathbb{Z}$ and $x^3+y^3=3z^3$ then $xyz=0$.
Source: ...
11
votes
1answer
7k 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
4
votes
3answers
485 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 ...
4
votes
5answers
678 views
Show that $3p^2=q^2$ implies $3|p$ and $3|q$
This is a problem from "Introduction to Mathematics - Algebra and Number Systems" (specifically, exercise set 2 #9), which is one of my math texts. Please note that this isn't homework, but I would ...
5
votes
2answers
962 views
Local-Global Principle and the Cassels statement.
In a recent article I have read, i.e. " Lecture notes on elliptic curves ", Prof.Cassels remarks in page-110 that
There is not merely a local-global principle for curves of genus-$0$, but
...
148
votes
12answers
42k 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. Converted
...
88
votes
3answers
3k 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?
Much later addendum: ...
23
votes
13answers
2k 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 ...
8
votes
3answers
556 views
$x^3+48=y^4$ does not have integer (?) solutions
How does one find all positive integer solutions to the equation $x^3+48=y^4$?
11
votes
2answers
846 views
Every even integer can be expressed as the difference of two primes?
Every even integer can be expressed as the difference of two primes?
If so, is there any elementary proof?
13
votes
2answers
823 views
Why is the decimal representation of 1/7 “cyclical”?
1/7 = 0.(142857)...
with the digits in the parentheses repeating.
I understand that the reason it's a repeating fraction is because 7 and 10 are coprime. But this...cyclical nature is something ...
8
votes
2answers
171 views
How can I prove my conjecture for the coefficients in $t(x)=\log(1+\exp(x)) $?
I'm considering the transfer-function
$$ t(x) = \log(1 + \exp(x)) $$
and find the beginning of the power series (simply using Pari/GP) as
$$ t(x) = \log(2) + 1/2 x + 1/8 x^2 – 1/192 x^4 + 1/2880 x^6 - ...
6
votes
4answers
627 views
Proving that an integer is the $n$ th power
I have not been able to solve this problem. Any insights would be appreciated!
Let $x, n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_{k}$
such that $x − a_k^n$ is ...
8
votes
3answers
1k views
Fibonacci sequence divisible by 7?
Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$.
I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
4
votes
1answer
487 views
Sine values being rational
Can $$\sin r\pi $$ be rational if $r$ is irrational? Either a direct or existence proof is fine.
3
votes
1answer
369 views
Prove that the class number of $\mathbb{Z}[\zeta_3]$ is $1$
How does one prove that the class number of $\mathbb{Z}[\zeta_3]$ is $1$?
1
vote
4answers
485 views
How can I prove that all rational numbers are either terminally real or repeating real numbers?
I am trying to figure out how to prove that all rational numbers are either terminally real or repeating real numbers, but I am having a great difficulty in doing so.
Any help will be greatly ...
4
votes
1answer
167 views
Why is the square of all odds less than an odd prime $p$ congruent to $(-1)^{(p+1)/(2)}\pmod p$?
I came across the two congruences that for $p$ an odd prime,
$$1^2\cdot 3^2\cdot 5^2\cdots (p-2)^2\equiv (-1)^{(p+1)/(2)}\pmod p$$
and
$$2^2\cdot 4^2\cdot 6^2\cdots (p-1)^2\equiv ...
23
votes
3answers
1k views
Subjects studied in number theory
I know little about number theory even after reading its Wikipedia article.
I was wondering if the subjects
studied by number theory is only
about integers or even more
restrictedly natural numbers ...
22
votes
2answers
2k 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 ...
18
votes
3answers
1k views
Find taxicab numbers in $O(n)$ time
This is a final exam question in my algorithms class:
$k$ is a taxicab number if $k = a^3+b^3=c^3+d^3$, $a,b,c,d$ are distinct positive integers. Find all taxicab number $k$ such that $a,b,c,d < ...
15
votes
6answers
2k views
prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer
Prove that $(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 first n even ...
6
votes
3answers
489 views
How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers?
How many rationals of the form $\large \frac{2^n+1}{n^2},$ $(n \in \mathbb{N} )$ are integers?
The possible values of $n$ that i am able to find is $n=1$ and $n=3$, so there are two solutions ...
3
votes
4answers
616 views
Not understanding Simple Modulus Congruency
Hi this is my first time posting on here... so please bear with me :P
I was just wondering how I can solve something like this:
$$25x ≡ 3 \pmod{109}.$$
If someone can give a break down on how to do ...
2
votes
2answers
723 views
$n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $n \mid \frac{a^{n}-b^{n}}{a-b}$
How does one prove that if $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $ \displaystyle n \mid \frac{a^{n}-b^{n}}{a-b}$ where $a,b, n \in \mathbb{N}$.
What i thought of is to consider $$(a-b)^{n} \equiv ...
