# Questions tagged [congruences]

The congruences tag has no usage guidance.

**11**

votes

**3**answers

355 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

**0**answers

182 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

280 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

286 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

150 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

213 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

180 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

137 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

49 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

328 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}$...

**1**

vote

**0**answers

88 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

150 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

121 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

147 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

328 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

**4**answers

321 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

**2**answers

236 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 ...

**11**

votes

**1**answer

1k 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

**0**answers

81 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$...

**34**

votes

**2**answers

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

**2**answers

278 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

**1**answer

249 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

**1**answer

298 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

**1**answer

140 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

**1**answer

144 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

**1**answer

304 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

**1**answer

202 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
...

**11**

votes

**2**answers

823 views

### Ramanujan's tau function, $691$ congruence, and $\eta(z)^{12}$

Let $q = e^{2\pi i\,z}$.
I. 24th power
The Ramanujan tau function $\tau(n)$ is given by the expansion of the Dedekind eta function $\eta(z)$'s $\text{24th}$ power. Then
$$\begin{aligned}\eta(z)^{...

**4**

votes

**2**answers

307 views

### Order of a matrix congruent to the identity modulo p

I couldn't find a demonstration of this theorem:
Given $A \in SO_2(\mathbb{Z}[{1 \over q_1},\dots,{1 \over q_k}])$
and $p$ prime $\notin \{q_1,\dots,q_k\}$
$\exists n \in \mathbb{N} : A^n=Id$ and $A\...

**3**

votes

**1**answer

347 views

### Solvability of Diophantine equation using congruences where the variables are bounded?

In page 2 of Mordell "Diophantion equations" it is given a necessary condition for the solvability of a Diophantine equation:
Integer solutions of the inhomogeneous equation $f(x) = 0$ can exist only ...

**7**

votes

**2**answers

758 views

### Some equalities involving prime powers

Let $p,a,b,x,y$ be positive integers where $p$ is an odd prime; $x$ and $y$ are odd; $p,x$ and $y$ are all coprime. I'm interested in finding examples of such numbers that satisfy this equation:
\...

**0**

votes

**0**answers

60 views

### Counting different residue classes of certain form modulo $4abc-1$?

I posted http://math.stackexchange.com the question and after a while I did not received any reply, so I thought maybe I re-post it here again, maybe some people are interested.
I like to calculate ...

**36**

votes

**2**answers

5k views

### What did Yu Jianchun discover about Carmichael numbers?

There's a news story going around (see for example [1]; other accounts are even more breathless) about an amateur mathematician, Yu Jianchun, finding an "alternative method to verify Carmichael ...

**1**

vote

**0**answers

241 views

### Computational number theory

Suppose that $p$ is prime and $q$ is an even number divides $p-1$, such that $q<\frac{p-1}{q}$ and $u$ has order $q$ modulo $p$. Let $S$ be the subgroup of $Z^*_p$ consisting of the powers of $u$. ...

**0**

votes

**0**answers

113 views

### Monoid prime ideals and prime congruences

I was wondering what the connection is between the notion of "prime congruence" on a monoid, and the notion of "prime ideal" in a monoid. Starting from a prime ideal $P$ in a monoid $M$, one can ...

**4**

votes

**3**answers

452 views

### On a theorem of Hensel about congruence of binomial coefficient

In the paper Binomial coefficients modulo prime powers, Andrew Granville stated the following theorem:
Let $n, m$ and $r=n-m$ be three given positive integer and $p^k$ is the exact power of $p$ ...

**5**

votes

**1**answer

236 views

### Up to $2000$, $A145722(n-1) \equiv \sigma(4n-3) \pmod{5}$

A145722 is
Expansion of f(q) * f(q^5) / phi(-q^2)^2 in powers of q where f(), phi() are Ramanujan theta functions.
Using the pari program and offset 0, up to $2000$...

**5**

votes

**1**answer

249 views

### For a sufficiently large $a$, are there distinct (mod $a$) integers such that all powers up to the $n$-th are “close” modulo $a$?

Given $n\in\Bbb N$ is there an $a_n\in\Bbb N$ such that for every $a>a_n$ there are two distinct integers $0<b<c<a$ such that $b^i\bmod a,c^i\bmod a\in(\sqrt a,\sqrt a\log a)$ for every $i\...

**7**

votes

**1**answer

640 views

### Is $n=6$ the only integer satisfies ${\sigma}_x(n) \equiv 0\bmod{n}$ for every odd integer $x > 0$ and $2 (\bmod n)$ if $x$ is even integer?

After a few computations in wolfram alpha about the divisor function for some values of $n$ to look the behavior of $\sigma_x(n)\bmod n$ for $\,n=6,\,$ i got this result : $\sigma_x(6)=0 \bmod 6$ for $...

**13**

votes

**1**answer

966 views

### On cubic reciprocity for $x^3+y^3+z^3 = 996$?

I. The Diophantine equation,
$$x^3+y^3+z^3 = 3w^3\tag1$$
with $x\geq y \geq z$ and $w=1$ has only two known solutions, namely $1,1,1$ and $4,4,-5$. Are there larger ones? As Noam Elkies points out ...

**0**

votes

**0**answers

397 views

### Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be:
$A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$
where A ...

**2**

votes

**0**answers

99 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$ ...

**11**

votes

**2**answers

1k views

### Is there a fixed integer $x>1$ satisfing ${\sigma}^{k}(x)\equiv 0\pmod{x}$ for all positive integers $k$?

This question related to this question from SE. I'm interested to know if there exists an integer $x>1$ that satisfies $${\sigma}^{k}(x)\equiv 0\pmod{x}$$
for all positive integers $k$.
Note. $\...

**19**

votes

**2**answers

1k views

### A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I
state it in a different but equivalent form. Let $a(n)$ be the sequence
at http://oeis.org/A131868, that is,
$$ a(n) =\frac{1}{2n^2}\...

**2**

votes

**1**answer

348 views

### Trying to prove a congruence for Stirling numbers of the second kind

This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement.
Proposition: When $n$ and $m$ are ...

**2**

votes

**1**answer

200 views

### Cardinality of the prime divisor set of a k-power sum

Let $a_{1},\dots,a_{n}$ be positive natural numbers ($n>2$) such that $a_{i}\neq a_{j}$ if $i\neq j$. I want to prove that
$$ \left\lvert \left\{ p \text{ prime} \; : \; p \mid \sum_{i=1}^n a_{i}^{...

**7**

votes

**1**answer

862 views

### Roots of a polynomial in a finite field related to Fermat's Last Theorem

In my class, we proved the following condition: define the polynomial $P_l(x)$ as
$$P_l(x) = \sum_{r=1}^{l-1}{\frac{1}{r}x^{l-1-r}}$$
Then if for all $a \in \mathbb{Z}/l\mathbb{Z}-\{0,1\},$ $P_l(x)$...

**19**

votes

**1**answer

1k views

### Does $\binom{2n}{n} \equiv 2 \pmod p$ ever hold?

Well, the title does not tell the whole story; the complete question is:
Are there any primes of the form $p=2n(n-1)+1$, with integer $n\ge 1$, such that
$$ \binom{2n}{n} \equiv 2\pmod p ? $$
...

**11**

votes

**1**answer

547 views

### A congruence conjecture regarding $(r-s)^4-1 \equiv 0\!\pmod{4r^2s}$

Is the following conjecture true?
Conjecture. If $r > s \ge 1$ are relatively prime integers such that
\begin{equation}
(r-s)^4-1 \equiv 0\!\pmod{4r^2s}, \tag{1}
\end{equation}
then $r-s = 1$ ...

**0**

votes

**2**answers

372 views

### What are all positive integers n for which the congruence $a^{n+1} \equiv a (mod n)$ holds? [closed]

Fermat's little theorem says that the congruence $a^p \equiv a (mod p)$ if $p$ is a prime number. $a^{n+1} \equiv a (mod n)$ works for all integers $a$ and some positive integers $n$, how can we ...