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)

1
vote
0answers
68 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)}$ ...
1
vote
0answers
65 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 ...
1
vote
0answers
63 views

solutions to $f(y) = n(n + 1) \ldots (n + m - 1)$

I was reading a paper about solutions to $f(y) = P(m)$, where $f(y) \in \mathbb Z[y]$ and $P(m) = n(n + 1) \ldots (n + m - 1)$ is a product of $m$ consecutive integers ...
1
vote
0answers
258 views

Finding the maximum XOR metric

I'm trying to find a way to find n keys (x bits) where the XOR distance metric between them would be greatest. By XOR distance metric I just mean the value when two keys are XORed together. So for ...
1
vote
0answers
160 views

Query on Brahmagupta-Fibonacci Identity

According to Brahmagupta-Fibonacci Identity, for $p=q\cdot r$ we can prove if any two of the integers $p,q,r$ are of the form $a^2+n\cdot b^2,$ the third must of the same form This is probably a ...
1
vote
0answers
56 views

How can I solve this using BIT?

I found a nice math problem, but I still can't solve it, I tried to find one solution using google and found that it can be solve using the Binary Indexed Tree data structure, but the solution is not ...
1
vote
0answers
57 views

Ring of the residual classes $(\Bbb Z/p\Bbb Z)^\times$? $p$-adic integer?

In a recent question we raised the theorem: for a given prime $p$ and a given power $m$ the representation of any positive integer $n\in \Bbb N$ in the form: $$ n=(a_u p - b_u) \; p^m$$ is unique ...
1
vote
0answers
47 views

A question about the solutions of a diophantine equation

I would like to know if it's possible to find the solution of the following equation: $$x^k+y^h=z^{kh}$$ in which: $$\{x,y,z\}\subset\mathbb{N}$$ given $k$ and $h$ with: $$\{k,h\}\subset\mathbb{N}$$
1
vote
0answers
123 views

Pythagorean triples and the unit circle

use the lines through the point $(1, 1)$ to describe all the rational points on the circle $x^2+y^2=3$. Why isn't this possible?
1
vote
0answers
37 views

Computability of division of large numbers

What is the largest computable mathematical division in terms of the number of digits that can be handled by a typical desktop computer using the best available big number libraries, assuming input is ...
1
vote
0answers
83 views

Matching numbers by $f(x)=\frac{1}{x}$

Let $0<x \leq 1$, We define a function such that $f(x)=y=\frac{1}{x}$ which results $y \geq 1$ . We have infinitely many numbers between $0$ and $1$, so we can match any $x$ to a number $y$ greater ...
1
vote
0answers
84 views

Extending a rational entry matrix to an orthogonal matrix.

Suppose $M \leq N$ are positive integers and let $r_1,\ldots,r_M$ represent the rows of an $M\times N$ matrix $A$ in which: (i) the rows of $A$ are orthogonal and having the same norm, (ii) the ...
1
vote
0answers
34 views

How to show this space is complete?

Let $\mathbb F_q$ be the finite field of $q$ elements. We let $K_{\infty}$ to be the field of formal power series in $x^{-1}$ over $\mathbb F_q$. If $$ \alpha = \sum_{- \infty}^{t} a_i x^i, $$ then ...
1
vote
0answers
131 views

Modified Arithmetic-Geometric Mean

Let $\{x_n\}$ and $\{y_n\}$ be defined iteratively, $x_0:=\beta >1, \ y_0:= 1$ and $x_{n+1}= \frac{x_n+y_n}{2}$, $y_{n+1} = (x_n.y_n)^{\frac{1}{2}}$; i.e. they are respectively the arithmetic and ...
1
vote
0answers
47 views

Synthetic Division with mods

$x^4+x+1$/ $2x^2$+1 In $F_5$ (means mod 5) I said let the leading coefficient be 2. Since $3$ $*$ $2$ - $5$ $*$ $1$ $=$ $1$, choose 3 to multiply $3$($2x^2$ $+$ $1$)= $x^2$ + $3$ (this is ...
1
vote
0answers
162 views

Is zero a cluster point of $n\sin n$?

I have seen somewhere that if $0\le \alpha<1$, then zero is a cluster point of the sequence $n^\alpha \sin n, n=1,2,\cdots$. My question is what if $\alpha=1$? Or $\alpha>1$?
1
vote
0answers
58 views

Questions regarding the use of Index Calculus for finite fields and elliptic curves

Ok I have a few questions that hopefully some people can answer: For the Index Calculus applied to the Discrete Log Problem in $\mathbb{Z}_p^*$. I first thought that if we could find the ...
1
vote
0answers
32 views

deg of composition on supersingular curve

Let we have supersingular curve $E(\bar{\mathbb{F}_q})$. Let we have algebraic function $f \in \bar{\mathbb{F}_q}(E)$ with div($f) = \sum_{i=0}^{i=n}n_iP_i$. Then div$(f) \circ [q] = ...
1
vote
0answers
94 views

Frobenius endomorphism on supersingular elliptic curve

Let we have supersingular curve $E(\bar{\mathbb{F}_q})$. Is it true that for every point $P$ $q$-Frobenius endomorphism $\pi_q$ can be write as $A + [q]B$ where $P = A + B$? It is true if ...
1
vote
0answers
49 views

Is it always possible to find primes $p, q$ such that $\left(\dfrac{p}{q}\right)_n=\left(n,\dfrac{p-1}{f}\right)=1$?

I first provide a background, or the context, where this question arises. Skip it if one wants so. Background: In the book The Genus fields of algebraic number fields by Ishida, one finds the ...
1
vote
0answers
68 views

Consequencesof the Hadamard product expression of $L(s, \chi)$

I'm going through my lecture notes and I'm stuck on the proof of For any $t>0$ and primitive $\chi$ modulo $q$ $$\sum_{\rho=\beta+i \gamma: \Lambda(\rho, ...
1
vote
0answers
201 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
1
vote
0answers
57 views

Equivalence class of quadratic forms

There is a natural action of the Hecke modular group (cf wiki) $\Gamma_0(q)$ on the set of integral quadratic forms $\phi = aX^2 + bXY + cY^2$ of discriminant $\Delta$ such that $a \equiv 0 \pmod q$. ...
1
vote
0answers
304 views

Existence of Untouchable Betrothed Numbers

An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer (including the untouchable number itself). The first few untouchable ...
1
vote
0answers
96 views

Representing a fraction as a $p$-adic number

If we have the following $p$-adic number: $$2+3p+5p^2+2p^3+3p^4+5p^5+2p^6+3p^7+5p^8+.....$$ and I am trying to find what rational number this p-adic number represents. I have no idea as to how to go ...
1
vote
0answers
42 views

3SAT to Subset Sum

I am starting with a 3-CNF $F(x_1,...,x_n) = C_1 \wedge ... \wedge C_m$. First, ow do I show that there is no clause that contains both a variable and its negation? Then, I have the set of equations ...
1
vote
0answers
103 views

Solve the equation $x^4+y^4=d*z^2$

Solve the equation:$$x^4+y^4=d*z^2,$$ where $x,y,z$ are positive integers,and $d>1$ is a given square-free integer. I know if $p$ is an odd prime and $p|d,$ then $t^4\equiv -1 \pmod p$ is ...
1
vote
0answers
73 views

Euler product of $\frac{1}{\gamma}$

I am trying to calculate the euler product of $\frac{1}{\gamma}(n)$ where $\gamma(n)$ is the number of divisors of n. So I have that: $\displaystyle D_{\frac{1}{\gamma}(n)}=\prod_p \left ( 1+ ...
1
vote
0answers
70 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
1
vote
0answers
54 views

conversion from psi function to prime counting function

Can we convert $\psi(x)$ to $\pi(x)$ without using integrals. Also if $\psi(x)>\psi(y)$ when we can say that $\pi(x)>\pi(y)$ . It seems that $\theta(x)>\theta(y)$ so $\pi(x)>\pi(y)$ but ...
1
vote
0answers
45 views

Is it possible to generalize Ramanujan's lower bound for factorials when $\{\frac{x}{b_2}\} + \{\frac{x}{b_3}\} \ge 1$?

This is the second attempt at a proof. My first attempt had a flaw in its logic. After reviewing the mistake in logic, I believe that with a revised logic, the argument can be saved. The revision ...
1
vote
0answers
25 views

Proving Post Correspondence Decidable

Consider the Post Correspondence Problem in the case when the alphabet consists of just one character: $\sum = \{1\}$. How do I show that this problem is decidable? I was thinking of reducing it ...
1
vote
0answers
412 views

Sum of squares function

The function rk(x) denotes the number of ways an integer x can be expressed as the sum of squares of k integers [the integers can be positive, can be negative, can be zero]. What is the value of ...
1
vote
0answers
49 views

Tate twists and dual representations

Let $X$ be $\mathbb{Z}$-module of finite cardinality $n$ and $\mu_n$ the group of $n$th roots of unity in $\bar{K}$. Suppose further that $X$ carries a $G_{K}$-operation (the absolute Galois group). ...
1
vote
0answers
58 views

Integer factorization using discrete logarithms

I'm reading up on RSA and attacks on it. At the end of one section of the notes, it asks (without giving an answer) whether or not integer factorization is easy given an oracle which computes discrete ...
1
vote
0answers
110 views

ring of integers in a cubic extension of a cyclotomic function field

Let $K=\mathbb{Q}[\omega]$ where $\omega^2+\omega+1=0$ and let $R$ be the polynomial ring $K[x]$. Let $L$ be the field $K(x)[y]$ where $y$ satisfies $y^3=1+x^2$. Which is the integral closure of $R$ ...
1
vote
0answers
58 views

Embedding an $n$-simplex in $\mathbb{Z}^n$.

I am trying to understand the proof of embedding an $n$-simplex in $\mathbb{Z}^n$ for specific values of $n$. The proof can be found here. I am stuck on what is meant by "the reflection with axis ...
1
vote
0answers
110 views

Efficient way for computation of derivatives of $f(x) = \zeta(1-x) + 1/x $ at integer x?

For some exercises with (divergent) summation of the Stieltjes constants I'm trying a formula, which involves derivatives of the $\zeta()$ -function at negative integers; perhaps better formulated as ...
1
vote
0answers
100 views

intuitive meaning behind Mertens' theorem

I have just been introduced the topic of distribution of primes, big O notation and aymptotic functions so please correct me if I say something that does not make sense. I am looking to get an ...
1
vote
0answers
117 views

The mathematics behind Sobol sequences

I am using Sobol sequence as random number generator in a computer program. Beyond just making the program work, I would like to learn the mathematics behind the Sobol sequence (and other ...
1
vote
0answers
50 views

sum over primes and its powers

are there examples in number theory where the series $$ \sum_{p} \sum_{m=-\infty}^{\infty}f(p^{m}) $$ or $$ \sum_{m=-\infty}^{\infty}f(q^{m}) $$ for fixed prime 'q' appear ?? i believe they may be ...
1
vote
0answers
155 views

The zeta-function of Fibonacci sequence?

I have been told that, for a given sequence ${N_r}$, its zeta-function is given by $exp(\Sigma _{r=1}^{\infty} N_rT^r/r)$. Since I have barely any experience with such a sum, I tried to find some ...
1
vote
0answers
73 views

Any work on properties of $N + \bar \phi (N)$?

I am looking for pointers to any existing materials about the properties of this quantity. For Euler's cototient, if a number $N$ is written as $2^a \cdot b$ with b odd then the cototient is $$\bar ...
1
vote
0answers
172 views

Pentagonal-Triangular numbers

Pentagonal Triangular Number is a number which is simultaneously a pentagonal number $P_n$ and triangular number $T_m$ . Such numbers exist when $$ \frac{1}{2}n(3n-1) = \frac{1}{2}m(m+1) $$ This ...
1
vote
0answers
64 views

$S$ unit equation

From experiments it seems $(1+\sqrt{2})^n+(1-\sqrt{2})^n=2^a-3^b$ has finite solutions $(a,b,n)$, where $a,b,n$ are non-negative integers. From $S$ unit equation we know ...
1
vote
0answers
98 views

Diophantine Equation: $f(x)f(y) = f(z^2)$ where $f$ is quadratic

In the study of the Diophantine Equation $f(x)f(y) = f(z^2)$ where $f$ is quadratic, the computational proofs I have seen (for specific $f$) rely on Pell's Equation. For example, if $f(t) = t^2+t+1$, ...
1
vote
0answers
45 views

Whether any 3 degree equtition (x,y) can transform to weierstrass equtition?

Whether any $a_1x^3+a_2y^3+a_3x^2y+a_4xy^2+a_5x^2y^2+a_6xy+a_7x^2+a_8y^2+a_9x+a_{10}y+a_{11}$ can transform to weierstrass equaition?
1
vote
0answers
90 views

Idealclassgroup for quadratic field

I have got a question about an ideal class group, namely the group of $\Bbb{Q}(\sqrt{-185})$. I can say the following: I can give a representant system of the group I can name the class number: ...
1
vote
0answers
285 views

Ramanujan's sums

Are the series expansions of arithmetic functions in terms of Ramanujan sums computationally useful? I didn't think they would be, but they seem to be good approximations even when summed with few ...
1
vote
0answers
132 views

Find total number of sets of integers which satisfy a given equality and inequality

Compute the total number of different sets of integers a1, a2,..,an which satisfy the following equality and constraints: $$ ...