Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

2
votes
1answer
53 views

Kronecker-Weber does not apply

Let $K=\mathbb{Q}(\sqrt{D})\neq \mathbb{Q}$. Show that $K$ has an abelian extension that is not contained in $K(\theta)$ for any root of unity $\theta$. Hint: Find $u \in K $ such that $K(\sqrt{u})$ ...
5
votes
0answers
108 views

Relative density of images of diophantine polynomials

My current research project involves sampling a sequence along non-constant polynomials with non-negative integer coefficients defined over the natural numbers, and I'd like to be able to say when two ...
2
votes
1answer
500 views

Every integer is congruent modulo $m$ to exactly one integer in $\{0, 1, …, m-1\}$

Show that every integer is congruent modulo $m$ to exactly one of the numbers in the set $\{0, 1, ..., m-1\}$. I tried this: Apply the division algorithm - then $n = q \cdot m+r$ where $q, r$ ...
3
votes
3answers
82 views

What is the ratio of all distinct fractions to all distinct pairs of naturals?

I've been thinking of this lately. Clearly, $|\mathbb{N}| = |\mathbb{N}\times\mathbb{N}|$ and the rationals are equal in count to the integers, which is equal in count to the number of integer pairs, ...
3
votes
2answers
122 views

Check if $u + v\sqrt 2 > u' + v'\sqrt 2$ without computing $\sqrt 2$

I'm building an algorithm that perform some computations on two inputs, m and n. These are numbers of the form $u + v\sqrt 2$, where $u$ and $v$ are integers. I'm asking here because at a certain ...
5
votes
4answers
394 views

Solutions to $p+1=2n^2$ and $p^2+1=2m^2$ in Natural numbers.

$$p+1=2n^2$$$$p^2+1=2m^2$$ Find positive integers $m,n$ and prime $p$ satisfying the above two equations. What would people commonly do? Subtracting both the equations. You get: ...
1
vote
0answers
49 views

Binomial coefficient formula: Why the dividend is a multiple of divisor [duplicate]

Looking at the formula for binomial co-effient, $$ \binom{n}{r}= \frac {n(n-1)...(n-r+1)}{ 1(2)(3)...(r)} $$ I am wondering why $ n(n-1)...(n-r+1) $ is a multiple of $ 1(2)(3)...(r) $ . I ...
4
votes
1answer
174 views

Solve in integers $ (y^3+xy-1)(x^2+x-y)=(x^3-xy+1)(y^2+x-y)$

Solve in integers: $$ (y^3+xy-1)(x^2+x-y)=(x^3-xy+1)(y^2+x-y)$$ My idea: $$\Longleftrightarrow (y^3+xy-1)(x^2+x-y)-(x^3-xy+1)(y^2+x-y)=0$$ $$\Longleftrightarrow ...
1
vote
1answer
92 views

Series equivalent to $\sum p_k$

Looking at a theorem of Chebyshev, I noticed that $$\sum_{n=0}^{\infty} \sum_{p_k < n} \frac{(\log p_k)^n}{n!} = 2 + 3 + ...+ p_k.$$ Proof. Letting $x = \log p_k$ and writing out the expansion of ...
34
votes
1answer
1k views

Is $\sqrt1+\sqrt2+\dots+\sqrt n$ ever an integer?

Related: Can a sum of square roots be an integer? Except for the obvious cases $n=0,1$, are there any values of $n$ such that $\sum_{k=1}^n\sqrt k$ is an integer? How does one even approach such ...
3
votes
1answer
194 views

Solve $37x^2-113y^2=n$

Prove that if these equations : $$37a^2\equiv n\pmod {113}\tag 1$$ $$-113b^2\equiv n\pmod {37}\tag 2$$ $$37c^2\equiv 113\pmod {n}\tag 3$$ have integer solutions, then the equation $$37x^2-113y^2=n$$ ...
4
votes
2answers
248 views

What is the need for classifying numbers like integer, whole number etc?

what are the everyday life examples where we use the classification. I feel all the math behind the scenes(in computers weather etc ) is highly abstracted. I am looking for strong answers to tell the ...
3
votes
1answer
154 views

Question on integral closure in $\mathbb{Q}[\alpha]$

Let $\alpha$ be a root of $f(x) = x^{3} -2x +6$, $ \ \mathbb{K} = \mathbb{Q}[\alpha]$. Prove that $ O _{\mathbb{K}} = \mathbb{Z[\alpha]}$. What I've done: $f$ is irreducible, so ...
0
votes
4answers
3k views

Proof of the statement “The product of 4 consecutive integers can be expressed in the form 8k for some integer k”

I am slowly diving into simple number theory and learning how to craft direct proofs. I needed to proof the statement "The product of 4 consecutive integers can be expressed in the form 8k for some ...
1
vote
2answers
170 views

Why isn't the factorial function defined for non-integers, but the gamma function is?

You cannot calculate n! when n is a non-integer, but you can calculate Γ(n+1) for non-integers when n! = Γ(n+1). Why?
2
votes
1answer
128 views

Problem related to Chinese Remainder Theorem

I'm not sure if there is a typo in the question or if I am incorrect (will point out as I get to it), but I am given that $a,b,m,n$ are integers with $\gcd(m,n) = 1$ and that \begin{equation} c \equiv ...
6
votes
1answer
112 views

Partitions of a prime power into powers of the same prime

Fix a prime $p$, and $k$ a natural number. The question is then: How many partitions of $p^k$ are there into powers of $p$? So, for instance, if $p = 2$ and $k = 2$, there are 4, namely (4), (2, 2), ...
9
votes
5answers
243 views

When does $a \cdot\sin(x) = \sin(a \cdot x)$?

I am examining the expression $a \cdot \sin(x) =\sin(a \cdot x)$ where $a$ is a rational constant. Is there a way to determine which values of $x$ would be valid? Does it only hold true for certain ...
1
vote
1answer
43 views

Number of rays on finite grid?

Let's have a set $M = \{ (i,j) : i,j \in \{0,\dots,m\}\}$. Define equivalence on $M$, $(i,j) \sim (k,l)$ iff there is $r \in \mathbb R$ that $(ri,rj) = (k,l)$. Question is what is the number ...
0
votes
1answer
192 views

Infinitely many primes of the type 5 mod 6.

Problem: Prove that there are infinitely many primes of the type 5 mod 6. My professor did the problem and the proof was horribly long. Can someone show me a shorter version of the proof of this ...
4
votes
2answers
150 views

Limiting value of $\lim \frac{1}{k}\sum_{n=1}^k \frac{p(n+1)-p(n)}{\log p(n)}$

Empirically it seems $$\lim_{k\to \infty} \frac{1}{k}\sum_{n=1}^k \frac{g(n)}{\log p(n)} = 1\tag{1} $$ in which p(n) is the nth prime and g(n) is the prime gap $p(n+1)-p(n).$ Cramer conjectured ...
1
vote
0answers
37 views

The number of sets of size k, containing distinct numbers $\leq m$, which sum to $n$

$$Y(n,m,k) = \left|\{s \mid s \in \mathcal P (\{1,2,3...m\}),Sum(s) =n, |s| = k \}\right|$$ Is what I'm going for. Does anyone know if this function has a name? Or if there's an algebraic formula ...
1
vote
2answers
109 views

Does $f(n)\sim g(n)$ imply $\lim_{k\to\infty} \frac{1}{k} \sum_n f(n)/g(n) = 1$?

Is it true that $$\lim_{k\to\infty}\frac{1}{k}\sum_{n=1}^k \frac{f(n)}{g(n)} = 1 \leftrightarrow f(n)\sim g(n).$$ My thought: $f(n)\sim g(n) \rightarrow \frac{1}{k}\sum \frac{f(n)}{g(n)} = 1$ since ...
6
votes
1answer
343 views

Why do no prime ideals ramify in the extension $\mathbb{Q}(\sqrt{p }, \sqrt{q})/\mathbb{Q}(\sqrt{pq })$?

Let $p,q $ be odd integer primes, $p \equiv 1 \pmod 4$ and $q \equiv 3 \pmod 4$. $K = \mathbb{Q }[\sqrt{pq }]$, $L = \mathbb{Q}[\sqrt{p }, \sqrt{q} ]$. Why a prime ideal in $O_{K}$ doesn't ramify in ...
0
votes
1answer
73 views

Smallest n digit number that can divide a n digit number

Is there any simple way to find the smallest n digit number that can divide n digit number. For Example: Lets take a two digit number xx. I want to find the smallest two digit(yy) number that can ...
3
votes
1answer
143 views

A generalization of Waring's problem

Let $f(x)$ be a polynomial with integer coefficients such that $$\lim_{x\to +\infty}f(x)=+\infty.$$ Is it true that there always exist two integers $K$ and $R$ (depend on $f(x)$), such that every ...
2
votes
1answer
167 views

Limit of $\sum\frac{1}{p(\pi(n))}$

Let $p(n)$ be the nth prime and $\pi(n)$ the number of primes not exceeding n. I wonder if we can show that $$\tag{1} S = \sum_{n= 2}^k \frac{1}{ p (\pi (n))} \sim \log k. $$ We know by comparison ...
12
votes
5answers
3k views

Why does one counterexample disprove a conjecture?

Can't a conjecture be correct about most solutions except maybe a family of solutions? For example, a few centuries ago it was widely believed that $2^{2^n}+1$ is a prime number for any $n$ . For ...
8
votes
8answers
558 views

Why is the Fibonacci ratio though a decreasing function, it is alternating and decreasing?

I tried to find the ratio of consecutive terms of the Fibonacci series and found that it is a decreasing function and it converges . I tried it though a small code piece in python so that I can have a ...
15
votes
2answers
328 views

Sum of irrational numbers, a basic algebra problem

Let $x_1,\dots,x_n$ be positive rational numbers. If $\sqrt[l_1]{x_1},\dots,\sqrt[l_n]{x_n}$ are all irrational numbers (where $l_1,l_2,\dotsc,l_n\in\Bbb N^*$), does it follow that $$\sqrt[l_1]{x_1}+ ...
1
vote
2answers
190 views

For a positive integer $n$, $p_n$ denotes the product of the digits of n, and $s_n$ denotes the sum of the digits of n.

For a positive integer $n$, $p_n$ denotes the product of the digits of $n$, and $s_n$ denotes the sum of the digits of $n$. What is the number of integers between 10 and 1000 for which $p_n + s_n = n$ ...
0
votes
3answers
56 views

find $0 < l < 35$ such that $l^5 \equiv 3\pmod {35} $

I have to find some $0 < l < 35$, such that $l^5 \equiv 3\pmod {35} $. I tried to use suggestions from my previous question, So I tried: $l^5 \equiv 3\pmod {35} $ => $35 | l^5 - 3$, I ...
11
votes
1answer
392 views

Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
2
votes
1answer
156 views

There is a real number $\alpha >1$ such that $\Bigl\lfloor2^{2^{{.}^{{.}^{{.}^{2^{\alpha }}}}}}\Bigr\rfloor$ is prime for all $n\geq 1$

Theorem: There exists a real number $\alpha >1$ that if $$\alpha =\alpha _0,\quad 2^{\alpha _0}=\alpha _1,\quad \dots\quad 2^{\alpha _n}=\alpha _{n+1},\quad \dots$$ then for all $n\geq ...
-1
votes
1answer
116 views

Beal's conjecture again: $(A^x + B^y)^3 = C^3$

$$(A^x + B^y)^3 = C^3$$ How do I write this out on the left side to show taking it to the 3rd power? $A=4$ and $x=12$ $B=7$ and $y=5$ $C$ is a prime number
2
votes
0answers
158 views

Number of ideals in a ring of algebraic integers with bounded norm

Let $K$ be a number field and $\mathcal{O}_K$ to be the ring of algebraic integers. I was wondering if there is some sort of asymptotic formula or bound for say number of ideals in $\mathcal{O}_K$, ...
2
votes
1answer
164 views

Are there any algorithms or methods to compute Landau function $g(n)$?

The details about Landau function can be found in A000793. Maybe there is some methods in A000793, but I don't understand what it says. If possible, can someone illustrate the method?
7
votes
3answers
269 views

The ordinary generating function for $ζ(s)$

$$\zeta(s)^m = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$$ where $ζ(s)$ is the Riemann zeta function has the ordinary generating function: $$\sum \limits_{n=1}^{\infty} a_nx^n = x + {m \choose 1}\sum ...
1
vote
1answer
86 views

How many divisors of $n$ are less than or equal to $m$?

Can I calc it in less than $O(\sqrt{n})$ time?
2
votes
1answer
1k views

Sum of the first n Prime numbers

Let $P_i$ denote the i-th prime number. Is there any formula for expressing $$S= \sum_{i=1}^m P_i.$$ We know that there are around $\frac{P_m}{\ln(P_m)}$ prime numbers less than or equal to $P_m$. ...
3
votes
1answer
100 views

Are there infinitely many $n$ such that $n$ and $2n+1$ are both prime numbers?

It seems that there are many such $n$. For example, the following are such $n$'s under $4000$. 2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 ...
0
votes
1answer
51 views

Show that if $b\mid c$ and $b > \gcd(c, d)$, then $b\nmid d$.

I have no clue about how to go about this question. I feel like I need more info, but I don't know, please help.
1
vote
2answers
136 views

Prove that $\gcd(a, b) = 1 ⇒ \gcd(a^2, b^2) = 1$ [duplicate]

I have a question from a sample exam I find difficults to solve: Prove that if $\gcd(a, b) = 1 ⇒ \gcd(a^2, b^2) = 1$ . I don't have any idea how to start. I'd like to get helped. thanks!
1
vote
1answer
441 views

About two consecutive integers which are sum of squares

I am looking for all two consecutive integers A and A+1,which can be represented as sums of two squares $A=a^2+b^2$ and $A+1=c^2+d^2$, $a,b,c,d>0$
0
votes
1answer
69 views

Is there a general solution to $n (a)^2=b^2+c^2+1$?

Is there a general solution to $n (a)^2=b^2+c^2+1$? Where $n$ is an integer and $a,b,c$ are rational numbers? I am looking for all rational solutions.
3
votes
0answers
90 views

Find integers $a$ and $b$ such that $a^5b+3$ and $ab^5+3$ are both perfect cubes of integers? [duplicate]

Are there integers $a$ and $b$ such that $a^5b+3$ and $ab^5+3$ are both perfect cubes of integers? $a,b$ are distinct integers. P.S.: I think trying to find some special cases would not be helpful.
8
votes
2answers
135 views

Reference for relation between class number of $\Bbb Q[\sqrt{-p}]$ and partial quotients of $\sqrt p$

So in Ireland and Rosen's, "Classical Introduction to Modern Number Theory", they mention the following incredible fact at the end of Chapter 13, section 1. Suppose $p \neq 3$ and $p \equiv 3 \pmod 4$ ...
5
votes
1answer
160 views

Do there exist complex algebraic $α,β$ such that $α^β=π$ or $α^β=e$?

Given the algebraic operations and complex exponentiation $(a+bi)^{c+di}$ and logarithm, is it possible to derive $\pi$ and $e$? If one is derivable then so should be the other, as $e^\pi = ...
5
votes
3answers
353 views

Inverting the modular $J$ function

Klein's modular function $J(z)$ is defined and studied in e.g. Apostol's book Modular functions and Dirichlet series in number theory. Certain specific evaluations are available, for example, ...
0
votes
1answer
48 views

Why is the Jacobi symbol $(D/m) = (D/n)$ for certain $m,n,D$?

$m \equiv n$ mod $D$, $m,n >0$ and odd, and $D \equiv 0,1$ mod $4$, then $(D/m) = (D/n)$ I'm am sure that one can show this using quadratic reciprocity and the supplements. Any ideas?