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
0answers
24 views

Finite amount of consecutive smooth numbers

is there a short proof of the fact that there is a finite amount of consecutive smooth numbers (meaning Given a finite set B, there is a finite amount of pairs $n,n+1$ so that both can be expressed as ...
2
votes
0answers
33 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
2
votes
1answer
92 views

Asymptotics of “ugly” function elucidate Goldbach's conjecture?

Question We now define the following "ugly" function: $$ A_c(s,r,n,m) = \begin{cases} 1 & \text{ if only $sr+nm=2c$ } \\ 0 & \text{otherwise} \end{cases} $$ How does the ...
2
votes
0answers
61 views

Inequalities for the sum of all digits [closed]

Let $S(n)$ denotes the sum of all digits of the positive integer $n$ a) Prove, that $S(n) \le 5 \cdot S(2n)$ for every $n$. b) Prove, that there exist infinitely many $n$, with $S(n)>1996 \cdot ...
2
votes
0answers
47 views

Find all integer sets $a,b$ where $\gcd(a^2+a+1,b^2+b+1)=3$

How does one find all integer sets $a,b$ where $gcd(a^2+a+1,b^2+b+1)=3$? It appears that for $gcd(a^2+a+1,b^2+b+1)=3$ to be true, then $a\equiv b \equiv 1 \pmod 3$. Also, if $(a^2-a+1,b^2+b+1)=1$, ...
2
votes
0answers
46 views

How to generate primitive solutions to the equation $a^3 + b^3 = c^2$

The solution for this is that we are supposed to pick numbers x and y, then we can substitute them in the equation and obtain some z, which we then multiply the left side of the equation with to ...
2
votes
0answers
55 views

infinitude of primes with the form $n^2+1$ [closed]

Is there any progress in proving the infinitude of prime numbers of the form $n^2+1$ ?
2
votes
0answers
102 views

Number-theoretic asymptotic looks false but is true?

Question Let $p_r$ be the $r'th$ prime. Is it true that, $$\sum_{r=1}^\infty s^r \ln(p_r) \sim \frac{s}{(1-s)} $$ I know this looks bizarre but kindly consider the argument below. I'm also ...
2
votes
0answers
23 views

Square roots with composite modulus

How can I find $x$ that for given $a$ and composite $n$ satisfies the expression below? $$x^2 = a \mod n$$ In my particular case $n=2^{32}$: $$x^2 = a \mod 2^{32}$$ Mathematica comes with nice ...
2
votes
0answers
77 views

Primitive of Weierstrass $\wp$

Consider a lattice $L=\mathbb{Z}+\mathbb{Z}\tau$. Take the function $\xi(z) = \frac{-1}{z} - \sum_{w \in L\backslash \{0\}} \Big ( \frac{1}{z-w} + \frac{1}{w} + \frac{z}{w^2} \Big )$. Obviously this ...
2
votes
0answers
35 views

Quantitative aspect of Chebotarev Density Theorem

I recently learned the Chebotarev Density Theorem for global fields. As far as I have seen, all applications of CDT seem to focused around proving some set of prime ideals (or places in function ...
2
votes
0answers
51 views

Construction of Tate curve and formal schemes

In the notes websites.math.leidenuniv.nl/geom/tate.ps (and probably in other places), there is a construction of the Tate curve, where the steps are summarized below. 1) Take ...
2
votes
0answers
42 views

Euler's Totient Function in Other Rings

I'm looking for rings other than the integers on which we could define an interesting analogue of Euler's Totient function. E.g., on a Euclidean domain with norm $N$ we could let $\phi(x) = ...
2
votes
0answers
76 views

Fibonacci Numbers and the Harmonic Series

$$\sum_{k=1}^{n} \frac{1}{k}=H_n=\frac{p_n}{q_n}$$ Where $p_n,q_n$ are coprime intergers. The first few values for $p_n+q_n$ are $2,5,7,37,197,69,504,1041,9649$. When are $p_n+q_n$ Fibonacci ...
2
votes
0answers
59 views

Proof that the spectrum of prime distribution will give zeros of Riemann Zeta function

All: Many of us have read that the spectrum of prime distribution will give zeros of Riemann Zeta function. For example, Mazur and Stein's book: (http://wstein.org/rh/rh.pdf ) have many nice pictures ...
2
votes
0answers
43 views

Existence of an isomorphism $\Bbb{Z}_{n}^{\times} \rightarrow \Bbb{Z}_{\phi(n)}^{+}$

I am considering the multiplicative group of units modulo $n$ which I shall refer to as $\Bbb{Z}_{n}^{\times}$. I read somewhere that $$\Bbb{Z}_{n}^{\times} \cong \Bbb{Z}_{\phi(n)}^{+}$$ where ...
2
votes
0answers
66 views

Paper of Paul Erdös

I'm trying to understand On Arithmetical Properties of Lambert Series by Erdös, but am stuck on the first page. He states: Put $k=\left[(\log n)^{1/10}\right]$ and let $p_1,p_2,\ldots$ be the ...
2
votes
0answers
39 views

Number of $100$-element subsets with sum congruent to $1$ mod $5$

Given the set of first $2015$ natural numbers $\{1,2,3...,2015\}$. How many $100$-element subsets of this set are there such that the sum of the elements of the subset is congruent to $1$ modulo $5$?
2
votes
0answers
79 views

Integer factorization: How to explain those numbers?

I am getting a non primary number $d$ with two nontrivial factors and I am trying to find what they are. Basically I am trying to solve the Integer Factorization Problem in special case. I want to ...
2
votes
0answers
50 views

If $a^n+n^b\mid c^n+n^d$ for every $n$ then $c=a^k$ and $d=kb$ .

I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let $a,b$ be fixed positive integers . If : $$a^n+n \mid b^n+n$$ for every positive integer ...
2
votes
1answer
44 views

Catalan numbers derivation (quadratic part)

When deriving the Catalan numbers using generating functions, eventually you reach the step: $C(x) = 1 + xC(x)^2$ which means $xC(x)^2 - C(x) + 1 = 0$ Which, through the quadratic formula, means ...
2
votes
0answers
33 views

Modular Euler product?

We know the Euler product. $$\zeta (s)=\prod_{p}\frac{p^{s}}{p^{s}-1}$$ I wonder if there is formula or any kind of work for this kind of prime product below? $$\prod_{p\equiv a \ (mod \ ...
2
votes
1answer
51 views

Sum of squares using generating functions

I tried using generating functions to solve the sum of squares formula based on the recurrence $a_n = a_{n-1} + n^2$ with $a_0 = 0$. $$G(x) = \sum_{n=0}^{\infty} a_n x^n \\ G(x) - 0 = ...
2
votes
0answers
56 views

How to show this identity is true?

$$\left(\sum_{k=1}^{\infty}\frac{i^{\Omega (k)}}{k^{s}}\right)^{2}=\frac{\zeta (4s)}{\zeta (2s)}\frac{2^{s-1}}{i-2^{s-1}}$$ where $i=\sqrt{-1}$ and $\Omega (k)$ is the number of (not necessarily ...
2
votes
0answers
82 views

An interesting equation in natural numbers

Let $n$ be a fixed natural number. How to solve the following equation in natural numbers: $$ \frac{1}{x_1} + \frac{2}{x_2} + \cdots + \frac{n}{x_n} = 1 $$ (I can find many soltions but I am looking ...
2
votes
0answers
78 views

The longest known cycle length of generalized collatz $5x+1$ trajectory

The generalized collatz $5x+1$ trajectory, if $n$ is even then divide $n$ by $2$, and if $n$ odd then multiply $n$ by $5$ and then add $1$. For example if $n=3$, we have ...
2
votes
0answers
44 views

Finding a summation involving gcd

I am trying to evaluate the following sum: $$b\sum_{i=a}^b\frac{i}{\gcd(i,b)}$$ I have solved the problem if $a=1$ but I am clueless for the case when $a$ is not $1$. For $a=1$, I used the fact that ...
2
votes
0answers
43 views

Maps between Elliptic Curves and Points at Infinity

I was trying some exercises from Silverman's book Rational Points on Elliptic Curves 2nd ed. (2015), and got stuck at this problem. 1.22 Let $C$ and $W$ be the projective curves ($b,e \ne 0$) $$ C: ...
2
votes
1answer
19 views

Definition of singular solution of $f(\mathbf{x}) = 0$ in $p$-adic integers

Let $f(\mathbf{x}) \in \mathbb{Z}[x_1, ..., x_n]$ and consider the equation $f(\mathbf{x}) = 0$. I am wondering what exactly does it mean by "the equation $f(\mathbf{x}) = 0$ has a non-singular ...
2
votes
0answers
55 views

Lower bound for the values of cyclotomic polynomials evualuated at integers

Let $b,n \geq 2$ be integers and let $\Phi_n(b)$ be the value of the $n$-th cyclotomic polynomial evaluated at $b$. I've recently noticed by computer experiments that whenever $n$ is odd, we seem to ...
2
votes
0answers
80 views

Fermat's Last Theorem vs. Classification of Finite Simple Groups

No branches of mathematics are comparable, but for some question, I would consider Number Theory and Group Theory. These are (known to me) the branches of mathematics, which much much vastly developed ...
2
votes
0answers
57 views

Solve the congruence system

I'm asked to solve the following congruence system: $$ \begin{split} x &\equiv 2 \pmod{5}\\ 2x &\equiv 1 \pmod{7}\\ 3x + y &\equiv 4 \pmod{11} \end{split} $$ But I think that by ...
2
votes
0answers
28 views

Factor the RSA modulus $n = 3844384501$ knowing that $3117761185^2 \equiv 1 \pmod{n}$

As per the title, the task is to Factor the RSA modulus $n = 3844384501$ knowing that $$3117761185^2 \equiv 1 \pmod{n}\text{.}$$ $n$ being an "RSA modulus" means that it is a product of two ...
2
votes
0answers
27 views

Relation between representation of a number in an integer base and Fourier series representation of a periodic signal

I am not a Mathematician - am just a software developer though I did some "Math" back in the day as part of my undergrad studies millions of years ago. Recently I had to revisit Fourier analysis of ...
2
votes
1answer
62 views

Fast modular exponentiation when Euler's Theorem doesn't apply

I want to write an algorithm to reasonably efficiently calculate $a^L \pmod n$ where $a$ and $n$ are reasonably small (ten digits or so), and $L$ is unreasonably large (billions of digits). I can ...
2
votes
0answers
35 views

Average of a certain diophantine function

Yesterday I was browsing math.se and came across this question. It was answered by a few people and the best answer was already accepted so I just read the question and the solutions to it. Then I ...
2
votes
0answers
51 views

prove this inequality for sufficiently large n

Prove the following inequality for $n \geq 100$ $$\pi\bigg(\frac{\log (n^2+2n)}{\log 2}\bigg) < \pi(2n) - 1.5\pi(n)$$ $\pi(n)$ denotes to prime counting function
2
votes
1answer
56 views

Sum over divisors of gcd of two numbers

How can I calculate this sum? $\sum\limits_{d~|~(n_1, n_2)} \mu(d) \tau\left(\dfrac{n_1}{d}\right) \tau\left(\dfrac{n_2}{d}\right)$, where $(n_1, n_2)$ is gcd of $n_1$ and $n_2$, $\mu$ is Mobius ...
2
votes
0answers
65 views

Showing the positivity of $p$-adic density of zeroes of a polynomial

Let $f \in \mathbb{Z}[x_1, \ldots, x_n]$ and $p$ be a prime. Let $\nu_t(p)$ denote the number of solutions $\mathbf{x} \in ((\mathbb{Z}/p^t \mathbb{Z}))^*)^n$ to the congruence $$ f( \mathbf{x} ) ...
2
votes
0answers
24 views

Understanding the group structure of quotient group derived from elliptic curve group

I am working through some content in L.C. Washington's Elliptic Curves, Number Theory, and Cryptography and I am unsure about what the group structure of a certain group looks like. Some background: ...
2
votes
0answers
33 views

What does the equation $a^{-k} \pmod N$ or $a^{k+1} \pmod N$ do when $N$ is composite and $N = 4k+3$?

I was studying what the equation $a^{-k} \pmod p$ and $a^{k+1} \pmod p$ when $p$ is prime. It is not hard to show that both of those are square roots of $a$ in this special case. In this special case ...
2
votes
0answers
15 views

Field Trace Identities

Let $\mathbb{F}_q$ be the finite field with $p^n$ elements and consider the trace map $$\mbox{Tr}: \mathbb{F}_q\to \mathbb{F}_p,$$ where $$\mbox{Tr}(\alpha)=\alpha+\alpha^p+\alpha^{p^2}+\cdots ...
2
votes
0answers
38 views

There are infinite number of degree $1$ principal prime ideal in a ring of algebraic integers

Let $K$ be a number field. I was wondering how we know that there are infinite number of degree $1$ principal prime ideal of $K$. Context: This is related to an example of polynomial representing ...
2
votes
1answer
42 views

Greatest natural number which divides the determinant of a matrix

All elements of a 100 x 100 matrix ,A are odd numbers. What is the greatest natural number that would always divide the determinant of A? I have been able to show that it is always divisible by ...
2
votes
0answers
50 views

factoring numbers in $\mathbb{Z}[\sqrt{2}]$ into primes

How do I factor, say, 2 + 3$\sqrt{2}$ into primes in $\mathbb{Z}[\sqrt{2}]$? I know that primes are irreducible in $\mathbb{Z}[\sqrt{2}]$ and that units are of the form $\pm(1\pm\sqrt{2})^n$. How are ...
2
votes
0answers
31 views

Structure of $p$-torsion groups

Let $A$ be an abelian group whose elements have order a power of certain prime $p$, suppose the $p$-torsion elements are finite, must $A$ be of the form $$(\mathbb{Q}_p/\mathbb{Z}_p)^{\oplus r}\oplus ...
2
votes
0answers
48 views

How many squares in a row can be found in a quadratic progression?

If we have a polynomial of degree $2$ with rational coefficients, it may or may not be a square of a degree $1$ polynomial. Say we look at $f(0),f(1),f(2),\ldots$ and observe that they are all ...
2
votes
0answers
51 views

Is it possible to reduce Theory of Rationals to Theory of Natural Numbers?

Is the following possible ? $$ Th( \mathbb{Q}, +, \leq ) \leq^{\log}_m Th( \mathbb{N}, +, \leq )$$ I believe it is not possible since Natural Numbers are not dense. It is also not possible $$ Th( ...
2
votes
0answers
29 views

Archimedean Hecke Algebra for number fields

Suppose we have a $GL_1$ over a number field $F$. I am interested in a description for the archimedean Hecke algebra (always taking the maximal compact subgroup). We know will be the tensor product ...
2
votes
0answers
37 views

Using $\pi$ to number by X-mas presents

Context: For this X-max, I will make $50$ presents by myself for my family. I would like to label them so that the labels are totally ordered and all different. However, I think that the traditional ...