# Questions tagged [congruences]

The congruences tag has no usage guidance.

98
questions

**1**

vote

**1**answer

78 views

### Can a polynomial be evaluated from evaluations of partial interpolations? (Or: can the unique solution of congruences be written in a certain way?)

Formally, let $K$ be a field, $a \in K[x]$, $D \subseteq K$, and $E = \{(x_i, a(x_i)) \mid x_i \in D\}$ be distinct evaluations of $a$ where $\lvert E\rvert > \operatorname{deg}(a)$ (so $E$ ...

**2**

votes

**0**answers

46 views

### Solution distribution in a quadratic congruence

Fix a modulus $M$. For varying $m$, consider the (possibly empty) set $R_{m,M}$ of roots of $x^2\equiv m^2+2 \pmod{M}$.
Are there good known bounds on
$$\sum_{m\le M^{1/100}}\sum_{r\in R_{m,M}}\min(M^{...

**8**

votes

**1**answer

225 views

### On the determinant $\det[\gcd(i-j,n)]_{1\le i,j\le n}$

In Sept. 2013, I investigated the determinant
$$D_n=\det[\gcd(i-j,n)]_{1\le i,j\le n}$$
and computed the values $D_1,\ldots,D_{100}$ (cf. http://oeis.org/A228884). To my surprise, they are all ...

**7**

votes

**2**answers

333 views

### Is there a nonzero solution to this infinite system of congruences?

Is there a triple of nonzero even integers $(a,b,c)$ that satisfies the following infinite system of congruences?
$$
a+b+c\equiv 0 \pmod{4} \\
a+3b+3c\equiv 0 \pmod{8} \\
3a+5b+9c\equiv 0 \pmod{16} \\
...

**1**

vote

**1**answer

144 views

### A special congruence

For any $a, b\in\mathbb{N}$ with $a+2b\not\equiv 0\pmod 3$, we define $\delta(a, b)$ as follows:
\begin{align*}
\delta(a, b)={\left\{\begin{array}{rl}
1,\ \ \ \ &{\rm if} \ a+2b\equiv 1\pmod 3,\\
...

**6**

votes

**1**answer

342 views

### Numbers $k$ with $\{\binom nk:\ n\in\mathbb N\}$ dense in $\mathbb Z_p$ for any prime $p\le k$

Let $k$ be a positive integer and let $p$ be a prime. In my 2011 PAMS paper joint with my former student W. Zhang [Proc. Amer. Math. Soc. 139(2011), 1569-1577], we studied when $$S(k)=\left\{\binom nk:...

**8**

votes

**1**answer

195 views

### Subgroups of Sp(2g,Z) that map onto all Sp(2g,Z/m)

I stumbled into the following problem. I apologize for being a bit naive.
For $g\geq 3$, consider the group $\mathrm{Sp}(2g,\mathbb{Z})$ of symplectic square matrices of order $2g$ with integral ...

**3**

votes

**1**answer

133 views

### Solutions to nonhomogeneous quadratic equation mod $N$

Is there any way to find non-trivial solutions to the equation $x^2 + y^2 - x \equiv 0 \mod{N}$? There are clearly several trivial solutions, for example $(x, y) = (0, 0), (1, 0), (2^{-1}, 2^{-1}), (2^...

**1**

vote

**0**answers

77 views

### Probability of satisfying the congruent mod equation

I'm wondering about the probability of picking three different numbers $x,y,z$ out of the set $[50]=\left\{ 1,2,3,...,50\right\}$ satisfying the equation: $$xyz\equiv \gcd(x,y,z)\mod 7$$ I started out ...

**1**

vote

**0**answers

129 views

### An explicit solution to the congruence $x^2\equiv 14(\frac 3p)-(\frac p3)-12\pmod {p}$?

Let $p>3$ be a prime, and let $(\frac{\cdot}p)$ be the Legendre symbol. Then
$$14\left(\frac 3p\right)-\left(\frac p3\right)-12=\begin{cases}1&\text{if}\ p\equiv1\pmod{12},
\\-25&\text{if}\ ...

**18**

votes

**0**answers

664 views

### Two curious series for $1/\pi$

On Jan. 18, 2012 I conjectured that for any prime $p>3$ we have
$$R_p^2\equiv\frac1{10}\left(512\left(\frac{10}p\right)-27\left(\frac{-15}p\right)-475\right)\pmod p,$$
where $(\frac{\cdot}p)$ ...

**6**

votes

**0**answers

157 views

### Some conjectural congruences involving Domb numbers

The Domb numbers are given by
$$D_n=\sum_{k=0}^n\binom{n}{k}^2\binom{2k}k\binom{2(n-k)}{n-k}\ \ \ (n=0,1,2,\ldots).$$
Such numbers have combinatorial interpretation, see, e.g., http://oeis.org/A002895....

**0**

votes

**0**answers

23 views

### Eigenvector of $U |y \rangle \equiv |xy (mod N) \rangle$, when $ x \le N$ and $x, N$ coprimes

In the book quantum computing and quantum computation of Nielsen and Chuang, in the chapter relating to order-finding, they say that via a simple calculation, an eigenvector of $U |y \rangle \equiv |...

**6**

votes

**0**answers

185 views

### A conjecture involving $P_n=\prod_{k=1}^np_k$

For each positive integer $n$ let $P_n=\prod_{k=1}^n p_k$, where $p_k$ is the $k$th prime.
Question. Is my following conjecture true?
Conjecture. For any integer $n>1$, there are $k,m\in\{1,\...

**1**

vote

**0**answers

88 views

### On the smallest solution of a linear congruence

I have the following question. First, consider the following congruence for primes $p\geq 5$:
$24x\equiv -1\;(\mbox{mod}\;p)$.
The smallest $x$, that is, $1\leq x\leq p-1$ for which the above ...

**0**

votes

**0**answers

168 views

### When is $\phi(a^n+b^n+c^n)=0\mod n$?

A corollary Zsigmondy's Theorem leads to the following congruence (one can look to $(24)$),$\phi(a^n+b^n)=0\mod n$ whenever $a, b$ are coprime and $n \neq 2$ and $(a,b)\neq(1,1)$. (Here $\phi$ is the ...

**0**

votes

**0**answers

75 views

### Set of primes $p_{1}\equiv 3 \bmod p_{2}$ such that $\phi(2^{\frac{{p_1}-3}{p_2}}-1)\equiv 0 \bmod p_1$ with $p_1,p_2\equiv 3\bmod 4$?

let $p_1$ and $p_2$ be positive primes such that $p_1,p_2 \equiv 3\bmod 4$
and $\phi$ is the Euler totiont function , I want to find the Set of primes $p_{1}\equiv 3 \bmod p_{2}$ such that $\phi(2^...

**0**

votes

**1**answer

94 views

### Solve congruence equation where unknown variable is in both sides of congruent operator

I am trying to solve the following equation:
$(a*n + c) \mod (b-n) \equiv 0$
and $n$ must be the lowest value in $[0, b-1]$
for example $a=17$, $c=-59$ and $b=128$, the solution is $n=55$
$n=b-1$ ...

**4**

votes

**0**answers

128 views

### Is it true that $|\{k^{k+1}+(k+1)^k\pmod p:\ k=0,\ldots,p-1\}|=(1-e^{-1})p+O(\sqrt{p})\ ?$

For each prime $p$, let us define
$$w_p:=|\{k^{k+1}+(k+1)^k\pmod p:\ k=0,\ldots,p-1\}|,$$
where $a\pmod p$ denotes the residue class $a+p\mathbb Z$.
Based on my computation, I conjecture that
$$w_p=...

**6**

votes

**1**answer

189 views

### Corollaries of the halo conjecture that do not involve the eigencurve

In the theory of p-adic modular forms there is a certain construction called the Coleman-Mazur eigencurve. The spectral halo conjecture roughly states that if you remove a closed subdisc of the weight ...

**3**

votes

**0**answers

144 views

### Congruences of modular forms modulo other modular forms

Congruences between modular forms are certainly a big topic in number theory, maybe with
$$E_{p-1}\equiv 1 \mod p \qquad \text{for a prime }p\geq 5$$
as the easiest example. Sometimes, $p$ might be ...

**6**

votes

**0**answers

200 views

### Two conjectural congruences for Franel numbers

Recall that the Franel numbers are given by
$$f_n:=\sum_{k=0}^n \binom{n}{k}^3\ \ \ (n=0,1,\ldots).$$
Question. How to prove my following conjecture?
Conjecture. For each odd prime $p$, we have
$$\...

**7**

votes

**0**answers

180 views

### Does Morley's congruence characterize primes greater than $3$?

In 1895 Morley showed that $$\binom{p-1}{(p-1)/2}\equiv(-1)^{\frac{p-1}2}4^{p-1}\pmod{p^3}$$
for any prime $p>3$.
In 2009, I formulated the following conjecture concerning the converse of Morley's ...

**2**

votes

**0**answers

49 views

### Is it possible to deduce statements for odd perfect numbers from the convolution sums involving divisor functions or other arithmetic functions?

Dividing and using some identities of [1] I've deduced the following facts, see also the remarks below. After these introductory paragraphs, to motivate our question, I am asking if we can deduce some ...

**1**

vote

**1**answer

131 views

### Chinese Remainder Theorem for Remainder Intervals

Given $n$ natural numbers $m_1,\dots,m_n$ and $n$ remainder intervals $[a_1,b_1],\dots,[a_n,b_n]$ holding $a_i < b_i$ for all $i\leq n$ the task is to search for the smallest natural number $x$ ...

**3**

votes

**0**answers

155 views

### An attempt to get a variant of Agoh–Giuga conjecture

The idea of this post is an attempt to explore a variant of the so-called Agoh–Giuga conjecture. In past days, and today, I tried to think about variants of this conjecture exploring congruences about ...

**7**

votes

**0**answers

190 views

### How to prove the identity $\sum_{k=1}^\infty\frac{3H_{k-1}^2+4H_{k-1}/k}{k^2\binom{2k}k}=\frac{\pi^4}{360}$?

For each $n=0,1,2,\ldots$, the harmonic number $H_n$ is given by
$$H_n:=\sum_{0<k\le n}\frac1k.$$
In 2016 I conjectured that
$$\sum_{k=1}^\infty\frac{3H_{k-1}^2+4H_{k-1}/k}{k^2\binom{2k}k}=\frac{...

**2**

votes

**0**answers

87 views

### $\varphi(m+n)\mid n$ for some positive integer $n$

Let $\varphi$ be Euler's totient function.
If $p$ is a prime, then $\varphi(1+n)=n$ for $n=p-1$.
Question. Is it true that for each integer $m>1$ there is a positive integer $n\le m^2-m$ such that ...

**1**

vote

**1**answer

154 views

### A divisibility problem involving Catalan numbers

The Catalan numbers in combinatorics are given by
$$C_n=\frac1{n+1}\binom{2n}n=\binom{2n}n-\binom{2n}{n+1}\ \ (n=0,1,2,\ldots).$$
In 2014 I formulated the following conjecture.
Conjecture. For each $...

**5**

votes

**0**answers

267 views

### Is an algebraic number satisfying certain super-congruences a root of unity?

Let $K|\mathbb{Q}$ be a number field, $D$ its discriminant and $\mathcal{O}$ the ring of integers in $K$. Let $x\in K$ (or maybe $\in \mathcal{O}[\frac 1D]$) such that for all primes $p$ in $\mathbb{Q}...

**1**

vote

**0**answers

44 views

### Efficient scissors congruence between efficiently describable convex polytopes and simplex?

Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...

**5**

votes

**1**answer

288 views

### Reversing the CRT: Is $5$ tough?

Given odd primes $p\ne q$, by the CRT we can find an integer $x$ such that $x\equiv 2^{p-1}\pmod q$ and $x\equiv 2^{q-1}\pmod p$. Can this procedure be reversed?
For which integers $x$ there exist ...

**1**

vote

**0**answers

60 views

### Wieferich primes and arithmetic prgressions

Let $p$ be an odd prime number. Let $K$ be a number field with Galois group $G$ and $H$ be a subgroup of $G$ stable under conjugation. Then the Cebotarev density theorem gives that $$\mathcal{L}=\{\...

**1**

vote

**1**answer

93 views

### Density of a set of numbers dividing a fixed number with polynomial exponent

Fix a positive integer $a>1$ and let $f\in\mathbb{Z}[x]$ be a polynomial with positive leading coefficient. We define a set $S$ of positive integers,
$$
S=\{n\in\mathbb{Z}^+:n\mid a^{f(n)}-1\}.
$$
...

**2**

votes

**1**answer

164 views

### Number of odd elements in a vanishing sum of binomial coefficients

Let $n$ be a positive integer, $k$ a non-negative integer and $N(n,k)$ be the number of odd elements among the numbers $\binom{n+k}{j}\binom{-n-k}{n-j}$, $0\le{j}\le{n}$, which sum to $0.$ It seems ...

**12**

votes

**4**answers

1k views

### Prove that $\sum_{n = 1}^{p - 1} n^{p - 1} \equiv (p - 1)! + p \pmod {p^2}$ with $p$ being an odd prime

First, I have to admit that I have already asked the same question on MSE several days ago. If I am bending any rules, I apologize for that and moderator can delete or close this question without ...

**9**

votes

**1**answer

321 views

### On the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo $p^2$

Let $p$ be an odd prime. It is well-known that
$$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$
I'm curious about the behavior of the permanent $\text{per}[i^{j-...

**3**

votes

**2**answers

398 views

### On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Motivated by Question 316142 of mine, I consider the new sum
$$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$
for any positive integer $n$, where $S_n$ is the symmetric group of all the ...

**4**

votes

**2**answers

376 views

### Non-torsion part of the abelianisation of congruence subgroups

I've posted this question on math.stackexchange, but haven't gotten any responses so I'm trying here instead.
Let $A = F_q[T]$ be the ring of polynomials in one variable with coefficients in a finite ...

**2**

votes

**1**answer

173 views

### On the function $f_m(p)=\left|\left\{1\leqslant k<\frac p2:\ \left\{\frac{k^m}p\right\}>\frac12\right\}\right|$

Let $m>1$ be an integer and let $p$ be an odd prime. Can we say something nontrivial about
$$f_m(p):=\left|\left\{1\leqslant k<\frac p2:\ \left\{\frac{k^m}p\right\}>\frac12\right\}\right|$$
(...

**7**

votes

**1**answer

235 views

### On $\prod^{(p-1)/2}_{i,j=1\atop p\nmid 2i+j}(2i+j)$ and $\prod^{(p-1)/2}_{i,j=1\atop p\nmid 2i-j}(2i-j)$ modulo a prime $p>3$

QUESTION: Is my following conjecture true?
Conjecture. Let $p>3$ be a prime and let $h(-p)$ be the class number of the imaginary quadratic field $\mathbb Q(\sqrt{-p})$. Then
$$\frac{p-1}2!!\prod^{...

**4**

votes

**1**answer

190 views

### On the solvability of the congruence $p^m\equiv m\pmod{n}$

Let $n,p\geq 1$ be integers, and assume that $p$ is a prime.
Question. Does there always exist an integer $m\geq 1$ such that
$p^m\equiv m\pmod{n}$?

**4**

votes

**0**answers

289 views

### Congruence for the product of quadratic residues + the product of quadratic non-residues

My question has been here on MSE for a long time, but it has not received a full answer. I bring it here:
Find a prime $p$ such that $p \equiv 1 \bmod 4$ and such that the
product in the range $[...

**1**

vote

**0**answers

70 views

### Equivalent condition for Poincare polynomial

I have found a statement in the introduction of the paper 'Sets of Recurrence and Generalized Polynomials' by Bergelson & Haland, which is
Result: Given a polynomial $p \in \mathbb{R}[x]$ such ...

**7**

votes

**1**answer

367 views

### On $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$

Euler's totient function $\varphi$ is multiplicative, and it plays important roles in number theory.
QUESTION: Is it true that for each integer $m>6$ we have $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$...

**4**

votes

**0**answers

196 views

### Number of power residues modulo prime power [closed]

Suppose you have a prime $p$ (not necessarily odd) and you have $\tau$ defined by $p^\tau \| k$ for some integer $k$. Then you define
\begin{equation}
y = \begin{cases}
\tau + 1 &, p > 2 \...

**5**

votes

**0**answers

192 views

### Cardinality of the image of a polynomial modulo $p^n$

Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial and let $p$ be a prime number. I'm looking for results about $$N_f(p^k) := \#\{(f(n) \bmod p^k) : n \in \mathbb{Z}\},$$ as $k \to +\infty$, where $...

**1**

vote

**0**answers

186 views

### Presentation of amalgamated sum as a quotient of the direct sum

I am currently reading Arthur Ogus' "Lectures on Logarithmic Algebraic Geometry" (https://math.berkeley.edu/~ogus/preprints/log_book/logbook.pdf).
I'm trying to understand why the amalgamated sum of ...

**6**

votes

**1**answer

158 views

### 2-adic valuation of $L(0,\chi)$ for a Dirichlet character

Let $\chi : (\mathbb Z/f\mathbb Z)^\times \to K = \mathbb Q(\mu_{\phi(f)})$ be a primitive Dirichlet character. Assume moreover that it is not quadratic, that is, $\chi^2$ is not the trivial character....

**1**

vote

**3**answers

337 views

### Finding a solution for this system of two diophantine equations (depending on a parameter) [closed]

I propose the following problem (Maybe it has a trivial solution):
Let $n$ be a positive integer such that $$n\equiv1 \pmod 4.$$
Then the problem is to find a rational $x$ as a function of $n$ such ...