All Questions
Tagged with congruences nt.number-theory
104 questions
1
vote
0
answers
98
views
Curious congruences modulo $4$ involving primes
We define
$$S(n)=\sum_{a=2+(n\pmod 2)}^{n-2}
\sharp(\{j,1\leq j<n \pmod{a},(a,j)=1\})\ .$$
(Searching the OEIS yielded no results.)
For $n>2$ we have the following experimental observations (...
- 17.9k
3
votes
0
answers
63
views
Congruences regarding $4n$-dimensional lattices
A sequence of integers $(a_n)_{n\geq 1}$ satisfies Gauss congruence if
$$\sum_{d\mid n}\mu(d)a_{n/d}\equiv 0\pmod{n}$$
for every $n\geq 1$. Such sequences are also called Dold sequences, Newton ...
- 111
3
votes
1
answer
439
views
Chinese remainder theorem for target interval
Given $n$ pairwise coprime natural numbers $m_{1}, \dots, m_{n}$ with remainders $y_{i}$, for all $i \leq n$. Furthermore, we have a target interval $I := \left[ a, b \right]$, with $1 \leq a < b \...
CommunityBot
- 1
1
vote
0
answers
152
views
A new Conjecture at OEIS sequence A376842
Here is a new conjecture of mine from the appendix of an unpublished manuscript currently under review.
Let $b \in \mathbb{Z}^+$ and assume that $n$ is an integer greater than $1$ and not a multiple ...
- 1,451
1
vote
1
answer
83
views
Complexity of solving system of binary quadratic equations modulo $3$
A special case of this question and
another question
What is the complexity of solving system of binary quadratic equations modulo
$3$?
$f_i(x_i,x_j)=0 \bmod 3, \deg{f_i}=2$.
Modulo $2$ can be ...
- 3,319
2
votes
1
answer
513
views
Prove ${^{b}a} \equiv {^{b+1}} a \pmod {10^{\lfloor{\log_{10} (^{b}a) }\rfloor + 1}} \Rightarrow a=5$ as $a$ and $b$ are two integers greater than $1$
$\DeclareMathOperator\len{len}$Let $a, b \in \mathbb{N} -\{ 0, 1 \}$ and define ${^{b}a}$ to be $a^a$ if $b = 2$ and $a^{\left(^{b-1}a \right)}$ if $b \geq 3$ (e.g., ${^{3}5} = 5^{\left( 5^5 \right)} =...
- 1,028
4
votes
0
answers
179
views
Congruences between hypergeometric functions coming from modular forms
Consider the formal power series
$${}_2F_1(1/12,5/12;1;z)^{24}-{}_2F_1(1/12,7/12;1;z)^{24}=-z/3-z^2/2-(320293/559872)z^3-\cdots$$
It follows from a theorem on modular forms that for $p\ge5$ the ...
CommunityBot
- 1
1
vote
1
answer
106
views
Number of solutions for linear modular equations given GCD
We are currently investigating a problem involving number theory, an area outside our field of expertise.
Let $n$ be a positive integer. Consider two pairs of integers $(j,k)$ and $(j′,k′)$ as ...
- 63.9k
4
votes
1
answer
252
views
About the exact origin of a binomial congruence
Given a prime $p$ and an integer $0 \leq k \leq p-1$, a famous congruence on binomial coefficients states:
$$\binom{p-1}{k} \equiv (-1)^k \pmod{p}$$
It is generally taught as a consequence of Pascal’s ...
- 12.3k
18
votes
2
answers
3k
views
Binomial supercongruences: is there any reason for them?
One of the recent questions, in fact
the answer
to it, reminded me about the binomial sequence
$$
a_n=\sum_{k=0}^n{\binom{n}{k}}^2{\binom{n+k}{k}}^2,
\qquad n=0,1,2,\dots,
$$
of the Apéry ...
- 1,446
0
votes
0
answers
129
views
Defining the number of rightmost frozen digits of Graham's number
It is well-known that (in radix-$10$) Graham's number, $G$, can be expressed as a tetration with base $3$ and a very large hyperexponent $\tilde{b}$. Thus, we can write that $\exists! \hspace{1mm} \...
1
vote
1
answer
252
views
A vanishing sum and related $p$-adic congruences
Recently I had a curious discovery. Namely, I have made the following conjectures.
Conjecture 1. We have the identity
$$\sum_{k=0}^\infty\frac{(10k-1)\binom{3k}k\binom{6k}{3k}}{(2k+1)512^k}=0.\label{1}...
- 528
8
votes
0
answers
351
views
A hypergeometric series for $\sqrt3\pi$ with converging rate $1/9$
Recently, I found a (conjectural) new series for $\sqrt3\pi$:
$$\sum_{k=1}^\infty\frac{(8k-3)\binom{4k}{2k}}{k(4k-1)9^k\binom{2k}k^2}=\frac{\sqrt3\pi}{18}.\label{1}\tag{1}$$
The series converges fast ...
- 15.6k
4
votes
0
answers
182
views
Computing the density of a set of multiples
Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
- 1,028
6
votes
2
answers
645
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$. ...
- 30.1k
12
votes
1
answer
838
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:...
CommunityBot
- 1
3
votes
0
answers
329
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,949
13
votes
1
answer
584
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$...
- 109k
5
votes
2
answers
510
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(...
- 121
3
votes
2
answers
710
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 ...
- 14.6k
2
votes
1
answer
148
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 ...
- 105k
0
votes
2
answers
132
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?
- 1,638
0
votes
0
answers
132
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 ...
- 1,451
1
vote
0
answers
176
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 ...
- 15.6k
5
votes
0
answers
541
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 ...
- 15.6k
4
votes
2
answers
214
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<...
- 15.6k
5
votes
0
answers
206
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
202
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}$ ?
...
- 14.6k
4
votes
2
answers
923
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)\...
- 34.3k
6
votes
1
answer
576
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 \...
- 260
8
votes
1
answer
407
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 $...
- 654
7
votes
2
answers
780
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 ...
- 687
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 ...
- 15.6k
5
votes
2
answers
348
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}+...
- 10.7k
3
votes
1
answer
172
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$ ...
- 10.7k
11
votes
1
answer
643
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 ...
- 17k
2
votes
0
answers
64
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
286
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 ...
- 105k
7
votes
2
answers
373
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} \\
...
- 5,103
9
votes
1
answer
357
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-...
- 34.3k
3
votes
1
answer
195
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,703
1
vote
0
answers
154
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}\ ...
- 15.6k
18
votes
0
answers
755
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)$ ...
- 15.6k
7
votes
0
answers
183
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....
- 15.6k
6
votes
0
answers
192
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,\...
- 15.6k
2
votes
0
answers
152
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
1
answer
243
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$ ...
- 54.2k
4
votes
0
answers
142
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=...
- 15.6k
7
votes
1
answer
342
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 ...
- 41
3
votes
0
answers
183
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 ...
- 37k