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
95 views

How prive this number theory $\sum_{k=1}^{p-1}kn_{k}\equiv \dfrac{1}{2}(p-1)(\mod p)$

let $p>3 $ is prime number,and $S=\{1,2,\cdots,p-1\}$,for every $k\in S$ there exist uniquely $x_{k}\in S$,such that $kx_{k}\equiv 1 (\mod p)$,that is $kx_{k}=1+n_{k}p,k=1,2,3,\cdots,p-1$ show ...
2
votes
1answer
335 views

Largest prime below a given number N

This came up as a part of algorithm puzzles: Given a number $N$, how to find the prime $P$ such that $P<N$ and the difference $N-P$ is minimum. For small $N$, simple sieves do work, but I'm unable ...
2
votes
1answer
75 views

$15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$

For which numbers $a$ is it true that if $15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$? I know that this means that $a\frac{15-c}{25}=k_1\in \mathbb{Z}$ and $\frac{15-c}{25}=k_2\in \mathbb{Z}$, but ...
2
votes
2answers
199 views

Infinite Integral Domains

Let $D$ be an infinite integral domain, and let $g,h \in D[X]$. Show that if $g(x) = h(x)$ for all $x \in D$, then $g = h$. I understand this means a one-to-one correspondence, but how do I go about ...
2
votes
1answer
36 views

$d$ to $1$ map, cyclic group and cosets

We know that $\mathbb{F}_p^{\times}$ is a cyclic group. Let $g$ be a prmitive root mod $p$, then the kernel of the map $\varphi:\mathbb{F}_p^{\times}\rightarrow \mathbb{F}_p^{\times}$ defined by ...
2
votes
3answers
531 views

About linear combinations of primes

$a,b,c$ are natural numbers whose greatest common divisor is $1$. $a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$ Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be ...
2
votes
1answer
90 views

Whether a domain is Dedekind or not

We know from algebraic number theory that if $d$ is a square-free integer, $d\neq 0,1$ and $d$ is congruent to $2,3$ modulo $4$ then $\mathbb{Z}[\sqrt{d}]$ is the ring of integers of the quadratic ...
2
votes
1answer
1k views

Can someone offer an intuitive understanding of linear/quadratic probing and double hashing?

I'm reading through Introduction to Algorithms, and I'm having trouble grasping intuitively how linear probing, quadratic probing, and double hashing exactly work. I suspect my confusion lies within ...
2
votes
1answer
109 views

Related to the partition of $n$ where $p(n,2)$ denotes the number of partitions $\geq 2$

I was trying the following question from the Number theory book of Zuckerman. If $p(n,2)$ denotes the number of partition of n with parts $\geq2$, prove that $p(n,2)>p(n-1,2)$ for all $n\geq 8$, ...
2
votes
2answers
56 views

using Dirichlet transforms to show infinity of primes

I am trying to understand the following lemma and its proof. The lemma and proof are on page 2 of this pdf: http://www.ias.ac.in/resonance/March2012/p284-290.pdf Basically, I want to know their ...
2
votes
1answer
162 views

Determining whether a form has a non-trivial zero

$f(x,y,z)=2x^2+3y^2-6z^2$. Determine whether the form has a non-trivial zero. (You do not need to exhibit it). I know that I need to use the Hasse-Minkowski Theorem somehow. From examples I've seen ...
2
votes
2answers
171 views

Roots of unity in $\mathbb{Q}(\zeta_p)$ for $p$ an odd prime

I am confused about a last step in a proof that the only roots of unity in $\mathbb{Q}(\zeta_p)$ are $\pm\zeta_p^j$, where $\zeta_p=e^{2 \pi i/p}$, $p$ is an odd prime and $1\leq j\leq p-1$. So far ...
2
votes
3answers
68 views

Constrictions on A.P with factorials.

There are five numbers $(a_1,a_2,a_3,a_4,a_5)$, such that they are in Arithmetic Progression. Given that $a_1$ and $a_2$ are factorials, is there a possibility that either $a_4$ OR $a_5$ is a ...
2
votes
1answer
57 views

Diophantine approximation problem

Denote $||x||=Min(x-[x],1-(x-[x]))$,it means the minimum distance between x and an integer. Can we find a fast algorithm to get a natural number $n$ that satisfies $$||na||<p,||nb||<p,...$$ ...
2
votes
1answer
142 views

Showing the sum over primes is equal to an integral

First, note that $$\vartheta = \sum_{p \leq x} \log p$$I am trying to show $$\vartheta(x) = \pi(x)\log(x)-\int_2^x\frac{\pi(u)}{u}du$$ I am trying to show this by summation of parts. The theorem of ...
2
votes
1answer
261 views

Explicit Formula for $\zeta(s)$

In the explicit expression for $$\psi_0(x) = x - \sum_{\rho} \frac{x^{\rho}}{\rho} - \frac{\zeta'(0)}{\zeta(0)} - \frac{1}{2} \log (1-x^{-2}) $$ $ x^\rho$ denotes $x^{\mathrm{Re} \rho}$. I wanted to ...
2
votes
1answer
86 views

show $k! = m^\alpha$ is impossible

I am not sure how to show that $$m^\alpha = k!$$ is impossible $\forall m,\alpha,k > 1$. I am supposed to use Bertrands theorem which states: There exists atleast one prime in the open interval ...
2
votes
2answers
72 views

Finding almost unique sets

Is there an efficient algorithm to find a group of sets, where all the sets each have the same number of elements and differ from each other by exactly one element, such that the number of unique ...
2
votes
1answer
355 views

A convergence problem: splitting a double sum

I have been facing some difficulties with the following question. For an absolutely convergent series $\sum_m a_m$, and the Möbius function $\mu(n)$, $x=(x_1,x_2)\in \mathbb{R}^2$, and $\alpha ...
2
votes
1answer
2k views

How to calculate $ 1^k+2^k+3^k+\cdots+N^k $ with given values of $N$ and $k$? [duplicate]

Here $ 1<N<10^9$ and $0<k<50$ So we have to calculate it in order of $O(\log N)$.
2
votes
1answer
235 views

RSA cryptosystem test question - help please!

Suppose that the 26 symbol alphabet $A,...,Z$ is used for all plaintext and ciphertext messages in an RSA cryptosystem. Suppose also that plaintext message units are length $2$ and ciphertext units ...
2
votes
1answer
73 views

How big is $Z_n^*$?

I would like to find some upper bound on $\frac{n}{|Z_n^*|}$ i.e. to show that many of the elements in $Z_n$ are also in $Z_n^*$. I want to show that $\frac{n}{|Z_n^*|}=O(log^cn)$ for some $c \in N$. ...
2
votes
1answer
181 views

How can I make n by adding k non-negative integers

Suppose I have 3 non-negative integers and I have to achieve 4 by adding these numbers .There are 15 ways to get 4 by adding 3 non-negative integers . They are ...
2
votes
1answer
131 views

Solving polynomials along with congruences

Say $g(x) = x^3 + x^2 − 5$. I need to show that for $i = 1,2,3,4,..$ There exists a unique $x_i \mod 7^i$ s.t $g(x_i) ≡ 0 \mod 7^i$ I am not sure how to go about this. Any ideas on where to ...
2
votes
1answer
46 views

Finding $a^b \pmod m$ where $b$ is large

Normally one would use Euler's Theorem for evaluating $a^{b} \pmod m$ where $m$ and $a$ are coprime, but what about when they are not coprime? Mainly, what about when $b$ is too large to store ...
2
votes
1answer
95 views

GCD inequality over numbers with the same set of prime factors

Suppose $m,n\in\mathbb{Z}^+$ have the same set of prime factors. Does it follow that $\gcd(m+1,n-1)\leq\gcd(m-1,n-1)+2$?
2
votes
1answer
90 views

Are there (known) bounds to the following arithmetic / number-theoretic expression?

I apologize in advance if this is something that is already well-known in the literature, but I would like to ask nonetheless (for the benefit of those who likewise do not know): Are there (known) ...
2
votes
2answers
137 views

Feature of the Pascal's triangle (OEIS A007318)?

If rows of Pascal's triangle (OEIS's A007318) after their content concatenation {1-1, 1-2-1, 1-3-3-1, 1-4-6-4-1, 1-5-10-10-5-1, 1-6-15-20-15-6-1, 1-7-21-35-35-21-7-1 and so on } be considered as ...
2
votes
1answer
49 views

Uniqueness up to sign of $L$ and $M$ in $p=\frac{1}{4}(L^2+27M^2)$.

If $p\equiv 1\pmod{3}$, it's well know that $p$ can be expressed as $$ p=\frac{1}{4}(L^2+27M^2). $$ A handful of places, like wikipedia, say that in this representation $L$ and $M$ are unique up to ...
2
votes
2answers
96 views

Behaviour of congruential generator

Define $X_{n+1} = (aX_n + c) \bmod m$ where $a$ is chosen uniformly at random from $\{1,\dots, m-1\}$ and $c$ is chosen uniformly at random from $\{0,\dots, m-1\}$ and $m$ is a fixed prime. Take ...
2
votes
1answer
107 views

Differences among different sieves encountered in sieve theory

Are the sieve techniques used in understanding the twin prime conjecture or other number theoretical conjectures different from sieve theory used in primality testing or integer factorization? What ...
2
votes
3answers
450 views

Solving a system of Pell and Pell-like equations

Solve (Find all the solutions, if there are, or prove there are not) the system of 2 Pell or Pell-like simultanous equations over the positive integers : $2b^{2}= a^{2} +1 = 3k^{2} + 2 $ with the 3 ...
2
votes
1answer
109 views

How to prove $A^x\equiv A^{x\: \bmod\: \varphi (c)+\varphi (c)}(\bmod\: c)(x\geq \varphi (c))$?

I want to calculate $A^B\bmod c$ (here $A$, $B$ and $c$ are all integers) and $B$ is very large like $10^{1000000}$ (such as a problem like FZU1759), and I have read many solutions about it but got ...
2
votes
1answer
263 views

Largest idempotent

Given the prime power factors of $N$, is there a non-quadratic algorithm for finding the largest idempotent of ring $\mathbb{Z}/N\mathbb{Z}$? (That is, the largest number $A \lt N$ such that $A^{2} ...
2
votes
1answer
106 views

Solving $ f(\log x)$

A generalization of the conjecture $$\pi(x+x^{\theta}) - \pi(x) \sim \frac{x^\theta}{\log x} $$ (Ingham, 1937 or earlier) might be $$\Delta \pi_k = \pi_k((x+1)^2) - \pi_k(x^2)\sim \frac{x}{\log ...
2
votes
1answer
594 views

Question about weight 2 Eisenstein series

I'm new to modular form, reading the book A First Course in Modular Forms We have the weight 2 Eisenstein series $$ G_2(\tau)=\sum_{c\in\mathbb{Z}}\sum_{d\in\mathbb{Z}_c'}\frac{1}{(c\tau+d)^2} $$ ...
2
votes
3answers
133 views

Solutions for $ 2^i = 3^ j - 1 $ or $ 2^i = 3^ j + 1 $

Are there any solutions for $ 2^i = 3^ j - 1 $ or $ 2^i = 3^ j + 1 $, for $i>3$ and $j>2$ ? Thanks! $:)$
2
votes
1answer
95 views

Factorization of $p\mathcal{O}_K$ in $\mathcal{O}_K$

Let $K=\mathbb{Q}(\alpha)$, where $\alpha$ is a root of $f(x)=x^3+x+1$. If $p$ is a rational prime. What can you say about factorization of $p\mathcal{O}_K$ in $\mathcal{O}_K$? I have this: The ...
2
votes
1answer
99 views

Why does a certain equality in Iwaniec's Topics in classical automorphic forms hold?

I have been reading the book Topics in classical automorphic forms for a while, where I encountered a formula in the middle of Sec 8.6 (p143) $$F(z;\beta,\gamma)=\frac ...
2
votes
1answer
94 views

How to calculate this sum of series?

Given, a series of polynomials $\{{b_r(x)}\}^{\infty}_{r=0}$ on $[0,1]$, such that $$b_{0}=1\;\;,b^{'}_{r}=rb_{r-1}(x)\;(r\ge 1)\;,\int^{1}_{0}b_{r}(x)dx=0\;(r\ge 1)$$ How can we prove ...
2
votes
2answers
512 views

Algorithm for finding many gcd(a,b) over a range of a?

I have a procedure where I calculate gcd(a,b) many times, and it can be computationally expensive. I am trying to instead create an array containing gcd(a,b) values by using a factor sieve of some ...
2
votes
1answer
136 views

Is there an iterative formula for the function $d(n)$?

Is there an iterative formula for the function $d(n)$ ? While d(n) is the count of divisors for n For example in Euler's totient function $ \phi(nm)= \phi(n)\phi(m) . \frac{d}{\phi(d)} $ where ...
2
votes
2answers
721 views

Sum of two squares $n = a^2 + b^2$ [duplicate]

Possible Duplicate: Prove that $n$ is a sum of two squares? Fermat’s theorem on sums of two squares Is there any elementary proof for this theorem: A number $n$ is a sum of two squares ...
2
votes
1answer
36 views

Counting points in a box modulo a number

Consider the positive integers $\leq x$, then we know that there are $x/p + O(1)$ integers $\leq x$ that are $a \pmod{p}$ ($p$ prime). Consider a similar problem, except this time, we are counting ...
2
votes
1answer
60 views

Finding an equation of solutions of an equation given constraints

$$\left(\frac{ax}{p_1}\right)^2 - \left(\frac{bx}{p_2}\right)^2 = cx \quad\text{and}\quad a\neq p_1, \, \, b \neq p_2$$where $a,b,c$ are nonzero integers, and $p_1$ and $p_2$ are distinct prime ...
2
votes
1answer
1k views

Partitions of an integer into k parts.

I am interested in knowing whether an exact formula (analogous to the Hardy-Ramanujan-Rademacher formula for $p(n)$) for the number of partitions of a positive integer into k parts is known. I tried ...
2
votes
2answers
757 views

Functional Equation. $f(mn)=f(m)f(n)$ and …

I want to prove the following. We have a function $f: \mathbb{Z} \to\mathbb{R}$ s.t. (1) $f(mn) = f(m)f(n)$ (2) $f(m+n) \leq f(m) + f(n)$ (3) $0 \leq f(x) \leq 1$ then $f(m+n) \leq \max\big(f(m), ...
2
votes
1answer
106 views

Absolute Convergence of Dirichelet Series

The exact series I must show converges absolutely is: $$\sum_{n=1}^{\infty}{\frac{d(n)^r}{n^s}}$$ for $s > 1$, $r\in \mathbb{N}$ and where $d(n)=\#\text{ of divisors of } n$. I've been able to ...
2
votes
1answer
402 views

How many ways are there of coloring the vertices of a regular $n$-gon

How many ways are there of coloring the vertices of a regular $n$-gon with all $p$ colors ($n,p \ge 2$), such that each vertex is given one color, and every color isn't used for two adjacent vertices? ...
2
votes
1answer
36 views

Find explicit constants $A$ and $B$ such that any solution of $x^3 + 2y^3 = m$ satisfies $\max\{|x|,|y|\} \leq A|m|^B$.

I am asked to find constants $A$ and $B$ such that any solution of: $$x^3+2y^3=m$$ satisfies $\max\{|x|,|y|\} \leq A|m|^B$. I am told to use the fact that: $$ \left| \frac{p}{q} - \sqrt[3]{2} \right| ...