Questions tagged [congruences]
The congruences tag has no usage guidance.
123
questions
6
votes
2
answers
622
views
Number of solutions of $am \equiv bn \pmod{q}$
Let $q$ be a (large) prime. Let $N$ be a positive integer of size${}\approx \sqrt{q}$. Let $\mathcal{M}$ be an arbitrary subset of $\{1, \dots, q\},$ such that $\mathcal{M}$ has cardinality $N$. ...
- 2,179
0
votes
0
answers
37
views
A question about algebraic indicator functions
Let $f \in \mathbb{Z}[x]$ and $m,k \in \mathbb{Z}$. Consider the indicator function $g_f : \mathbb{Z} \to \{1,0\}$ given by
\begin{align*}
g_f(n) =
\begin{cases}
1 &\text{if there exists $r \in \...
- 669
3
votes
1
answer
371
views
A combinatorial identity involving binomial coefficients
When I was reading an article by CHUN-GANG JI (A SIMPLE PROOF OF A CURIOUS CONGRUENCE BY ZHAO), he mentioned in the acknowledgement
the following identity
$$\sum_{i+j+k=p,\text{ } i,j,k\gt 0}{p\choose ...
- 33
3
votes
0
answers
281
views
When are modular forms linearly independent modulo $p$?
Let $M_2(\Gamma_0(N))$ be the space of weight $2$ modular forms for $\Gamma_0(N)$ and let $f_1, \dots, f_r$ be a basis of normalized eigenforms for $M_2(\Gamma_0(N))$. Given a rational prime $p$, I'll ...
- 1,799
5
votes
2
answers
244
views
Modulo $x^2 + y^2 - 1$, is every homogeneous polynomial that is a square of a polynomial, necessarily of sum of squares of homogeneous polynomials?
I am hoping this question is alright for Math Overflow. I didn't get a definitive solution in Math Stack Exchange.
Let $f(x, y) \in \mathbb{R}[x, y]$ be a homogeneous polynomial with real coefficients ...
- 253
13
votes
1
answer
540
views
A congruence for a product of binomial coefficients?
For every prime $p\geq 5$ one seems to have the congruence
$$(-1)^{(p-1)/2}\prod_{k=0}^{p-1}{p-1\choose k}\equiv 1-p+\frac{3}{2}p^2-\frac{7}{6}p^3\pmod{p^4}\ .$$
(I have checked all primes up to $5000$...
- 16.3k
4
votes
2
answers
196
views
"Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$
Given an integer $a$, I would like to build a table of entries $(p, \text{ord}_p(a))$, where $p$ runs over the prime numbers not dividing $a$ and not exceeding a fixed parameter $P$, and $\text{ord}_p(...
- 43
3
votes
2
answers
371
views
Binomial coefficient congruence modulo $p^n$
I am interested in the following congruence
$$\binom{ap^n}{bp^n}\equiv \binom{a}{b}\pmod{p^n}$$
I am aware that by some reference in a book the above it should actually hold modulo $p^{3n}$; the ...
- 847
7
votes
2
answers
219
views
Congruences of binomial sums
Let $a_n$ is a binomial sum, for example
$$
a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}
\quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\...
- 16.2k
2
votes
1
answer
92
views
Primitive representation of integers by some form on the genus of a quadratic form
Some time ago, I asked a question about equidistribution on a paper of Duke and Schulze-Pillot that was usefully answered.
However, on the answer there was a statement that was unimportant for me back ...
- 163
3
votes
1
answer
56
views
Reference request for a proof of the Mal'cev condition for congruence $n$-permutability
By a theorem of Hagemann and Mitschke, a condition (A) that a variety $\mathcal{V}$ is congruence $n$-permutable, is equivalent to a condition (B) that there exist ternary terms $p_1,\dots,p_{n-1}$ ...
- 133
0
votes
2
answers
124
views
Binomial congruence modulo prime [closed]
Let $a$, $b$ $(b≤a)$ be two positive integers are not twin primes and $p$ is any prime number.
Is this congruence
$$ \binom{a^p}{b^p} \equiv \binom{a}{b}^p \pmod{p} $$
valid?
- 15
0
votes
0
answers
112
views
Which consequences can be deduced from this peculiar property of tetration?
Recently (assuming radix-$10$), I showed that, for any $a \in \mathbb{N}_{0}$ that is not a multiple of $10$, there exists a unique value $V(a) \in \mathbb{N}_{0}$ which corresponds to the number of ...
- 688
1
vote
0
answers
170
views
Some $p$-adic congruences involving permutations
Motivated by my study of determinants and permanents, here I present several conjectures on $p$-adic congruences involving permutations.
As usual, we let $S_n$ be the symmetric group consisting of all ...
- 13.9k
5
votes
0
answers
469
views
Two conjectures for primes $p\equiv 1\pmod 8$
Motivated by my paper Quadratic residues and quartic residues modulo primes [Int. J. Number Theory 16 (2020), 1833-1858], here I pose two new conjectures for primes $p\equiv1\pmod8$ based on my ...
- 13.9k
2
votes
1
answer
125
views
Conjectural congruences for numbers related to Littlewood-Richardson coefficients
For $n \geq 0$, let $a_n$ be the square of the Euclidean length of the vector of Littlewood-Richardson coefficients of $\sum_{\lambda \vdash n} s_\lambda^2$, where $s_\lambda$ are the symmetric Schur ...
- 19k
4
votes
2
answers
209
views
Least modulus distinguishing some integers
I can deduce some results about this from the prime number theorem or from results about the primorial function $p\#$ but I'm wondering what the state of the art is:
Given integers $0\le a_1<a_2<...
- 24.1k
5
votes
0
answers
177
views
Number of solutions of linear congruence with bounded variables
Fix some nonzero integers $a_1, \dots, a_k$, with $k \geq 2$, and some real numbers $c_1, \dots, c_k \in (0,1)$.
For every positive integer $m$, let $N(m)$ be the number of $k$-tuple of integers $(x_1,...
- 121
4
votes
2
answers
195
views
System of congruences with bound condition
Let $m$ be a positive integer divisible by $6$, and let $q$ be one of $8,9$,
or a prime $\gt 3$.
Question : Is there always an $x\in [1,m]$, coprime to $m$, such
that $x\not\equiv\pm 1 \ \mod{q}$ ?
...
- 623
6
votes
1
answer
550
views
Are there finitely many primes $x$ such that for a fixed odd prime $p$, $n=x^{p-1}+x^{p-2}+\dotsb + x+1$ is composite and $x \mid \phi(n)$?
Let
\begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1
\end{equation} where $x$ and $p$ are odd primes.
If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \...
- 319
3
votes
2
answers
897
views
A conjecture about 433
Motivated by Question 405105, I found the following
Conjecture. $2^{2n}-2^n+1 \equiv 0 \pmod {433}$ and $n=4m$ iff
$$\phi(m) = \phi(i + j) = \phi(i) + \phi(j) ,$$
and
$$\phi(m) = \phi(ik) = \phi(i)\...
- 729
7
votes
2
answers
741
views
Could a nice principle be extracted from this lemma of Gauss
I asked the following question in the math SE, with a bounty of 200 pts, without result.
question:
To prove the quadratic reciprocity law, Gauss needed the following lemma:
If $p$ is a prime number ...
- 677
1
vote
0
answers
138
views
The congruence $\mathrm{per}[|j-k|]_{1\le j,k\le p}\equiv-1/2\pmod p$ with $p$ an odd prime
For a matrix $[a_{j,k}]_{1\le j,k\le n}$, its permanent is given by
$$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$
Let $p$ be an odd prime. I have proved the ...
- 13.9k
3
votes
1
answer
168
views
Does $\{\tau(1)\tau(2)+\cdots+\tau(n-1)\tau(n)+\tau(n)\tau(1):\ \tau\in S_n\}$ contain a unique multiple of $n^2$ for each $n\ge6$?
Motivated by Question 397575, here I pose a related question.
Question.
Does the set $$T_n:=\{\tau(1)\tau(2)+\cdots+\tau(n-1)\tau(n)+\tau(n)\tau(1):\ \tau\in S_n\}$$ contain a unique multiple of $n^2$ ...
- 13.9k
5
votes
2
answers
298
views
Permutations $\pi\in S_{p-1}$ with $\frac1{\pi(1)\pi(2)}+\frac1{\pi(2)\pi(3)}+\cdots+\frac1{\pi(p-2)\pi(p-1)}+\frac1{\pi(p-1)\pi(1)}\equiv0\pmod{p^2}$
A well known congruence of Wolstenholme states that
$$\frac1{1^2}+\frac1{2^2}+\cdots+\frac1{(p-1)^2}\equiv0\pmod{p}$$ for any prime $p>3$. For each $n=3,4,\ldots$ we clearly have
$$\frac1{1\times2}+...
- 13.9k
3
votes
1
answer
178
views
The invertible matrices $S$ that satisfy $A=SDS^T$
Any real symmetric matrix $A$ can be written as $A=SDS^T$ for some diagonal matrix $D$ and invertible matrix $S$. Let's fix $D$ to be the (diagonal) inertia matrix of $A$, which has an entry $1, -1, 0$...
- 1,000
10
votes
1
answer
591
views
A conjecture on binomial coefficients and roots of unity
Is the following true?
Let $p$ be a prime and let $w$ be a $(p-1)$st root of unity (not necessarily primitive). Then
$$\binom{w}{n}=\frac{w(w-1)\cdots(w-n+1)}{n!}$$ is $p$-integral; i.e., it can be ...
- 15.7k
1
vote
1
answer
87
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$ ...
- 539
2
votes
0
answers
61
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^{...
- 21
8
votes
1
answer
272
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 ...
- 13.9k
7
votes
2
answers
362
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} \\
...
- 403
1
vote
1
answer
156
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,\\
...
- 13
12
votes
1
answer
790
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:...
- 13.9k
8
votes
1
answer
298
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
176
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,683
1
vote
0
answers
144
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 ...
- 119
1
vote
0
answers
146
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}\ ...
- 13.9k
18
votes
0
answers
732
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)$ ...
- 13.9k
7
votes
0
answers
178
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....
- 13.9k
6
votes
0
answers
190
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,\...
- 13.9k
2
votes
0
answers
145
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 ...
- 21
0
votes
0
answers
178
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 ...
user147204
0
votes
0
answers
89
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^...
- 2,218
0
votes
1
answer
213
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$ ...
- 103
4
votes
0
answers
138
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=...
- 13.9k
6
votes
1
answer
299
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 ...
user145520
3
votes
0
answers
166
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 ...
- 11.8k
6
votes
0
answers
211
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
$$\...
- 13.9k
7
votes
0
answers
203
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 ...
- 13.9k
2
votes
0
answers
62
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 ...
