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)

11
votes
2answers
720 views

A problem about the largest prime factor of $n^2+1$

Let $f(n)$ be the largest prime factor of $n$. The image of function $g(n)=\sqrt{f(n^2+1)}$ is like this: Question: If we want to draw a horizontal line which bisects the points from $n=1$ to ...
0
votes
0answers
96 views

estimate $\sum_{x<p\le x+y} \log{p}/p$

In his paper the prime number theorem via the large sieve, A. Hildebrand made use of the following inequality $$\sum_{x<p\le x+y} \frac{\log{p}}{p} \le (2+o(1))\log{\frac{x+y}{x}}$$ where $x\ge y$ ...
6
votes
1answer
116 views

Is there always a prime $p$ so that the largest prime factor of $p^2+i$ not exceeding $p$ for $-k\leq i \leq k$?

Define $f(n)$=the largest prime factor of $n$. For example, $f(28)=7.$ Question: Is it true that for any given integer $k>0$, we can find a prime $p>\sqrt k$ so that $$f(p^2-k)\leq ...
1
vote
1answer
88 views

Fermat's little theorem special case

I am trying to prove a special case of Fermat's little theorem, but i am new to number theory, so i am stuck with this exercise...may i ask you for a little help? Let $k\in \mathbb{N}$, given are ...
9
votes
2answers
189 views

Polynomials mapping factorials to factorials

I'm looking for all polynomials $P(x)$ with integer coefficients such that for every $n \in \Bbb N$ there is an $m \in \Bbb N$ such that $P(n!)=m$!. The only solutions seem to be the constant ...
1
vote
1answer
77 views

Polynomial whose only values are squares

Given a polynomial $ P \in \Bbb Z [X] $ such that, $ P (x)$ is the square of an integer for all integers x, is $ P $ necessarily of the form $ P (x)= Q (x)^2$ with $ Q \in \Bbb Z [X]$?
2
votes
1answer
81 views

Why inverse modulo exponentiation is harder than inverse exponentiation without modulo

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. ...
19
votes
2answers
527 views

A simple way to obtain $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s}$

Let $ p_1 <p_2 <\cdots <p_k <\cdots $ the increasing list in set $\mathbb{P}$ of all prime numbers . By sum of infinite geometric series $\sum_{k=0}^\infty r^k = \frac{1}{1-r}$ for ...
5
votes
1answer
70 views

The minimal polynimial of a primitive $p^{m}$-th root of unity over $\mathbb{Q}_p$

Proposition 7.13 of Neukirch's ANT states that for a primitive $p^{m}$-th root of unity $\zeta$ (p prime) the extension $\mathbb{Q}_{p}(\zeta)/\mathbb{Q}_{p}$ is totally ramified of degree ...
4
votes
1answer
167 views

generalisations of Lagrange's four-square theorem

For which positive integers $a, b, c, d$, any natural number $n$ can be represented as $$n=ax^2+by^2+cz^2+dw^2$$ where $ x, y,z,w$ are integers? Lagrange's four-square theorem states that ...
9
votes
1answer
223 views

What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a ...
9
votes
0answers
230 views

Integer values of the Riemann Zeta function

When $s>1$ is real, the Riemann zeta function $\zeta(s)$ takes all finite positive value $> 1$. I am studying the values of $s$ for which $\zeta(s)$ is a positive integer. I have the following ...
3
votes
1answer
216 views

prime factors of numbers formed by primorials

Let $p,q$ be primes with $p \leq q$. The product $2\cdot3\cdot\dots\cdot p$ is denoted with $p\#$, the product $2\cdot3\cdot\dots\cdot q$ is denoted with $q\#$ (primorials). Now $z(p,q)$ is defined ...
3
votes
1answer
79 views

How do infinite series contain “local” information?

I would like to know why we consider infinite series (Dirichlet series, zeta function, elliptic curve $L$-series) or their Euler product. How is the local information "stored/contained" in the ...
2
votes
1answer
67 views

Fixed four degree reducible polynomial

How can I find the largest possible number of distinct integer values $\{x_1,x_2,\ldots x_n\}$, such that for a fixed reducible degree four polynomial with integer coefficients, $|f(x_i)|$ is prime ...
6
votes
4answers
304 views

Greatest integer $n$ where $n \lt (\sqrt5 +\sqrt7)^6$

I'm really not sure how to do this. I factored out a power of $3$ and squared so that I have $2^3 (6+\sqrt{35})^3 \gt n$ , and I know that if I can prove that $12^3-1 \le (6+\sqrt{35})^3 \lt 12^3$ I ...
2
votes
1answer
66 views

Limit approaching a pole of $\phi(s)=-\frac{\zeta'(s)}{\zeta(s)} - \sum_p \frac{\log p}{p^s(p^s -1)}$

If: $$\phi(s) = -\frac{\zeta'(s)}{\zeta(s)} - \sum_p \frac{\log p}{p^s(p^s -1)},$$ where $\zeta(s)$ is the riemann zeta function, why is: $$\lim_{\epsilon \to 0} \epsilon\phi(1+\epsilon) = 1\quad ?$$ ...
3
votes
2answers
726 views

If the difference of cubes of two consecutive integers is a square, then the square can be written as the sum of squares of two different integers.

How can i prove the statement that if the difference of cubes of two consecutive integers is an integral power of 2, then the integer with power 2 can be written as the sum of squares of two different ...
1
vote
2answers
75 views

The action of a Galois group on a prime ideal of a Dedekind domain

This is a slight variant of a question I asked earlier. Let $A$ be a commutative Dedekind domain and $K$ its field of fractions. Let $L/K$ be a finite Galois extension with Galois group $G$ and let ...
3
votes
1answer
126 views

What will be time complexity using dynamic programming

If I were to find a set of 10 positive integers whose sum = 87248 and the sum of their squares = 447804117. Using an efficient dynamic programming, what will be time complexity of this kind of ...
3
votes
0answers
105 views

The action of a Galois group on a prime ideal in a Dedekind domain

Let $A$ be a commutative Dedekind domain and $K$ its field of fractions. Let $L/K$ be a finite Galois extension with Galois group $G$ and let $B$ be the integral closure of $A$ in $L$. If ...
3
votes
1answer
116 views

Pell-like equations and continued fractions

Why does the continued fraction method work? Could be applied in order to solve, for example, $x^{17}-19y^{17}=1$ ?
2
votes
0answers
38 views

Least value of a multi-residue CRT

Given coprime moduli $m_1,\ldots,m_n$ with $k\ge2$ residues in each modulus, what is the least nonnegative value congruent to one of the specified residues to each modulus? Obviously it must be less ...
1
vote
2answers
79 views

Compute all the sets of 87248 into 10 parts

How many sets are possible? I have to compute all the sets of 87248 into 10 parts (Additional conditions which may be useful are: integers can be repeated, every integer is less than or equal to ...
1
vote
2answers
449 views

Does this system of congruences have a solution even if they are not relatively prime at first?

$$x \equiv 4\ (\textrm{mod}\ 15) \ \ \ \ \land\ \ \ \ \ x\ \equiv 6\ (\textrm{mod}\ 33)$$ Does this system of congruences have a solution even if they are not relatively prime at first? If I try to ...
2
votes
2answers
131 views

Is there an algorithm to find the number of digits in 2^n, where n is a positive integer?

Is there an algorithm to find the number of digits in 2^2030 ? $2^1=2$ $2^2=4$ $2^3=8$ $2^4=16$ $2^5=32$ $2^6=64$ $2^7=128$ ... $2^{10}=1024$
4
votes
3answers
157 views

Product of greatest common divisors

As usually, let $\gcd(a,b)$ be the greatest common divisor of integer numbers $a$ and $b$. What is the asymptotics of $$\left(\prod_{i=1}^{i=n} \prod_{j=1}^{j=n} \gcd(i,j)\right)^{1/n^2} $$ as $n \to ...
1
vote
1answer
127 views

Prime made from the digits of $\sqrt{22}$

Which is the smallest prime derived from the digits of $\sqrt{22}$, where the 4 before the comma is not considered ? To be more precise : $x:=\sqrt{22}-4$ , so $x = 0,690415...$ for every natural ...
4
votes
4answers
344 views

Sum of greatest common divisors

As usually, let $\gcd(a,b)$ be the greatest common divisor of integer numbers $a$ and $b$. What is the asymptotics of $$\frac{1}{n^2} \sum_{i=1}^{i=n} \sum_{j=1}^{j=n} \gcd(i,j)$$ as $n \to \infty?$
13
votes
1answer
489 views

Narcissistic numbers in other bases

It is well known that $153$ is a narcissistic number; that is, it is equal to the sum of the cubes of its digits since $153=1^3+5^3+3^3$. Other bases have similar numbers. For example, in base $3$, ...
1
vote
2answers
79 views

Need help in number theory

I wanted to know, how do I go about finding solutions to the equation $(x+1)(y+1) = z^3 + 1$ (integral solutions). Any help appreciated. Thanks.
7
votes
1answer
306 views

Is there a elementary proof that $3$ is not a congruent number?

How to show that $3$ is not a congruent number? I don't want to use Tunnell's theorem(1982). Is there a more elementary proof?Thanks a lot! There is proof in Judith D. Sally's book "Roots to ...
0
votes
3answers
138 views

Quadratic residues, mod 5, non-residues mod p

1) If $p\equiv 1\pmod 5$, how can I prove/show that 5 is a quadratic residue mod p? 2) If $p\equiv 2\pmod 5$, how can is prove/show that 5 is a nonresidue(quadratic) mod p?
0
votes
0answers
329 views

Norm map of unramified extension

Let $K \subset L$ be an abelian unramified extension of local fields. Is it true that norm map $N:\mathcal O_L^*\mapsto \mathcal O_K^*$ is surjective?
3
votes
0answers
149 views

question about riemann zeta function

How can one prove that $$\zeta (2n)=\frac{(-1)^{n-1}2^{2n-1}\pi ^{2n}B_{2n}}{(2n)!}$$ where $n\in N$ and how can one prove that $$\zeta (2n)=\frac{(-1)^{n}2^{2n-2}\pi ...
4
votes
1answer
237 views

Linear independence over rationals

I am trying to figure out for what values of $n$, the numbers $\sin\left(\frac{2\pi k}{n}\right)$, for $k = 1,\dots,n-1$, are linearly independent over the rationals. Any thoughts on how I may want ...
1
vote
0answers
76 views

$\theta(x) = O(x)$ in the prime number theorem

In the Newman short proof of the prime number theorem (http://www.maths.dur.ac.uk/~dma0hg/prime_number_theorem_zagier.pdf) Zagier states that the fact that $2^{2n} >= e^{\theta(2n) - \theta(n)}$ ...
7
votes
1answer
132 views

Find a number $A$ so that $\lfloor A^{3^n} \rfloor$ are always odd

Find a number $A$ so that (1) $\lfloor A^{3^n} \rfloor$ is always odd for $n\geq 1$;($\lfloor x \rfloor$ is the largest integer not greater than $x.$) (2) $A>1$ and $A^{3^n}$ is never an ...
4
votes
0answers
93 views

Linear independence of $\cos(n\theta)$

I was trying to see if the cosines of the (certain) integer multiples of a certain angle were linearly independent over $\mathbf{Q}$. In particular I was looking at when $\theta = ...
4
votes
0answers
97 views

Bounds for multi-dimensional Kloosterman Sums

I'm looking for a general bound (in terms of $p$) for the Kloosterman sum, working in $\mathbb{F}_{p}$, $$\sum\limits_{x_{1} \dots \ x_{n} = a} \psi(x_{1} + \dots + x_{n})$$ for $\psi$ a nontrivial ...
1
vote
2answers
125 views

Characteristic Primes of repunits

First off, we're working in base 10. A repunit is a number of form $111111...1$. ( n ones) For some integer sequence $(a_n)$, a charateristic prime $p$ of $a_n$ is a prime which divides $a_n$, but ...
2
votes
1answer
56 views

Difficulty with a meromorphic extension.

I'm trying to understand the prime number theorem, but never having followed a course in complex analysis, I have some difficulties. (the article is this: ...
0
votes
3answers
75 views

Index of a subgroup of $\mathbb{Z}\times\mathbb{Z}$

Let $p\in\mathbb{Z}$ be a prime and $u\in\mathbb{Z}$ be such that $u^2\equiv -1\pmod{p}$. Now define an additive subgroup $S$ of $\mathbb{Z}\times\mathbb{Z}$ by following, $$S:=\{ ...
54
votes
2answers
2k views

Is this similarity to the Fourier transform of the von Mangoldt function real?

Mathematica knows that the logarithm of $n$ is: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ The von Mangoldt function should then be: ...
1
vote
0answers
67 views

Order of summation of Moebius function with summations of fractional parts as coefficients

I want to show that $\displaystyle\sum_{i=0}^n\left(\mu(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\{jx\}\right)=O(n)$ for $x\in (0,1)$. I have tried to use the result that ...
3
votes
1answer
73 views

Prove that there are no integers $\csc {\frac{j\pi}{n}}-\csc{\frac{k\pi}{n}}=2$

Prove that there are no integers $j,k,n$ with odd $n$ satisfying $$\csc {\dfrac{j\pi}{n}}-\csc{\dfrac{k\pi}{n}}=2$$ This problem from $AMM,1999,10630$, but this solution is very ugly,and it's not ...
1
vote
1answer
65 views

Are there infinitely many Mersenne numbers coprime to a given integer?

That is, given a positive integer m, is the set $\{n\mid \gcd(m,2^n-1)=1\}$ where n is a positive integer infinite?
2
votes
1answer
169 views

Probability of 2 as a liar in the SPRP test - Miller-Rabin

I've used number-theoretic results for p(k, t) (e.g., DLP) to create a utility, mrtab, that generates the Miller-Rabin iterations (as a k-bit threshold table) required to satisfy a given ...
4
votes
1answer
739 views

Number of ordered pairs of coprime integers from $1$ to $N$

How many ordered pairs $(a, b)$ of positive integers $a$ and $b$ are there such that $\gcd(a, b)= 1$ and $1\leq a,b\leq N$? My approach is as follows. Note that $a= b$ only when $a= b= 1$. So this ...
4
votes
0answers
194 views

possible prime factors of $4^{444}+3$

I have not factored the number $4^{444}+3$ yet. I wonder, though, if there are restrictions for possible prime factors p. The only obvious restriction is, that -3 must be a quadratic residue of p. ...