Questions tagged [congruences]
The congruences tag has no usage guidance.
86
questions
6
votes
0answers
155 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
0answers
64 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
0answers
160 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
0answers
71 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
1answer
76 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
0answers
124 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
1answer
147 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 ...
2
votes
0answers
129 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
0answers
194 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
0answers
172 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
0answers
45 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
1answer
108 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
0answers
117 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
0answers
185 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
0answers
74 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
1answer
129 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
0answers
257 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
0answers
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
1answer
267 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
0answers
56 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
0answers
225 views
A Wolstenholme type congruence
Consider the following congruence: For $p\geq 5$ prime and every $n,\nu\in\mathbb{N}$ we have
\begin{align*}
0\equiv\sum_{k=1\atop p\nmid k}^{pn-1}\frac1k \binom{pn(\nu+1)-k-1}{pn\nu-1}
\mod p^{2(\...
1
vote
1answer
79 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
1answer
163 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
4answers
874 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
0answers
246 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
2answers
332 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
2answers
331 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
1answer
162 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
1answer
231 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
1answer
188 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
0answers
224 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
0answers
63 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
1answer
352 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}$...
3
votes
0answers
166 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
0answers
174 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
0answers
154 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
1answer
150 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
3answers
335 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 ...
5
votes
4answers
337 views
When does the following congruence identity hold?
Let $m$,$l$ be coprime integers where $m,l\geq 2$. For any integer $a$ and positive base $b \ (b\geq 2)$, let
$
[a]_b
$ denote the element of $\{0,\ldots, b-1\}$ that satisfies the equivalence
$[a]...
9
votes
2answers
247 views
For which values of $k$ is it known that there are infinitely many $n$, such that $2^{n+k}\equiv 1\pmod{n}$?
I know that there are no solutions to $2^n\equiv 1\pmod{n}$ for $n>1$ and I can prove that there are infinitely many $n$ such that $2^{n+1}\equiv1\pmod{n}$.
My question is:
Do we know other ...
12
votes
1answer
2k views
A good reference to the general Chinese Remainder Theorem
I am writing a paper on the topology of the Golomb space and need a good (standard) reference to the following
General Chinese Remainder Theorem. For integer numbers $a_1,\dots,a_n$ and positive ...
2
votes
0answers
90 views
“Close” roots of polynomials and Pillai property
A sequence of integers $a(n)_{n \geq 0}$ has the Pillai property if there exists an integer $G \geq 2$ such that for all integers $k \geq G$ there exists an integer $n \geq 0$ such that none of the $k$...
35
votes
2answers
2k views
Is the sum of digits of $3^{1000}$ divisible by $7$?
Is the sum of digits of $3^{1000}$ a multiple of $7$?
The sum of the digits of $3^{1000}$ can be computed using a computer. It is equal to $2142$, so the answer is positive.
Is there a short proof ...
11
votes
2answers
298 views
Harmonic congruence
There are a number of interesting congruences for harmonic sums, not the least of which is Wolstenholme's theorem: $H_{p-1}:=\sum_{j=1}^{p-1}\frac1j\equiv 0\mod p^2$.
It appears that $\sum_{j=1}^{p-1}...
4
votes
1answer
282 views
Matrix congruence
Let $A$ be an $n\times n$ matrix with integer entries and let $d_1,...,d_n|q$ all be given natural numbers (I am happy to assume that $q$ is a prime power).
How many solutions $x_1,...,x_n$ modulo $q$...
3
votes
1answer
307 views
Probability in $GL_2(\mathbb{Z}/p^{r}\mathbb{Z})$
My question may be not interesting or easy to answer ! but I am really not familiar with proba.
Let $p$ be an odd prime number. and let $r\geq1$ an integer. choose an element $A\in\mathrm{GL}_2(\...
1
vote
1answer
147 views
What is the general formula for $\# \{ 1 \leq a \leq q-2,| (a,q)=1, (a+2,q)=1 \}$
Let $q=\prod P_i^{k_i}.$
I have learned here that $\# \{ 1 \leq a \leq q-1| (a,q)=1, (a+1,q)=1 \}= F(q)=\prod (p_i-2)pi^{k_i-1}
= q\prod (1-2/p_i)$
Here was the idea behind it : For any $p_i$, there ...
-2
votes
1answer
149 views
Solve an equation with a factorial [closed]
x! - 2 = y^2.
Task: Solve over the naturals.
I think the answers are x = 3, x = 2, but I am not sure.
5
votes
1answer
342 views
About Morley congruence
Let $p>3$ be an odd prime and $a$ be a positive integer, is the following congruence true?
$$\binom{p^a-1}{\frac{p^a-1}{2}}\equiv(-1)^{\frac{p^a-1}{2}}4^{p^a-1}\pmod{p^3}.$$
When $a=1$, this is ...
2
votes
1answer
224 views
Efficiently lifting $a^2+b^2 \equiv c^2 \pmod{n}$ to coprime integers
Let $n$ be integer with unknown factorization. Assume factoring $n$
is inefficient.
Let $a,b,c$ satisfy $a^2+b^2 \equiv c^2 \bmod{n}, 0 \le a,b,c \le n-1$.
Is it possibly to lift the above
...
