Skip to main content
27 votes
Accepted

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

The result can be easily proved without using Bernoulli numbers. If $a$ and $b$ are integers not divisible by an odd prime $p$, then \begin{align}(ab)^{p-1}-1=&b^{p-1}(a^{p-1}-1)+(b^{p-1}-1) \\\...
Zhi-Wei Sun's user avatar
  • 14.6k
23 votes
Accepted

A good reference to the general Chinese Remainder Theorem

It seems that you are after this result which can be found, for example, as Theorem 3.12 in Gareth A. Jones, Josephine M. Jones: Elementary Number Theory, Springer-Verlag, London, 1998. Springer ...
Martin Sleziak's user avatar
23 votes
Accepted

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

Yes, this is true, as a consequence of an identity in a space of modular forms of weight $6$. The form $\eta(2z)^{12}$ is in this space; and $\sigma_5(n)$ for $n$ odd are the coefficients of the ...
Noam D. Elkies's user avatar
16 votes
Accepted

What did Yu Jianchun discover about Carmichael numbers?

Apparently it is an alternative proof of the infinitude of Carmichael numbers. The other proof mentioned in the articles ("done by academics 20 years ago") is: W. R. Alford, Andrew Granville, Carl ...
Myshkin's user avatar
  • 17.5k
16 votes
Accepted

A congruence for a product of binomial coefficients?

At first, $$(-1)^k{p-1\choose k}=\frac{(1-p)(2-p)\cdots (k-p)}{1\cdot 2\cdots k}=\left(1-\frac{p}1\right)\left(1-\frac{p}2\right)\cdots \left(1-\frac{p}k\right) \\\equiv 1-pe_1(1,1/2,\ldots,1/k)+p^2 ...
Fedor Petrov's user avatar
13 votes
Accepted

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

Denote $f(k)={\rm gcd}(k,n)$. Clearly $f$ is an $n$-periodic function. $D_n$ is the circulant $D_n=\det(f(i-j):0\leqslant i,j\leqslant n-1)$ which equals $\prod_{k=0}^{n-1}h(\omega^k)$ where $\omega=e^...
Fedor Petrov's user avatar
12 votes

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

The answer to your question as to whether $G=Sp_{2g}({\mathbb Z})$ is NO. $Sp_{2g}({\mathbb Z})$ contains a pro-finitely dense FREE subgroup (hence has infinite index) which is also finitely ...
Venkataramana's user avatar
12 votes
Accepted

"Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$

Order computations are generally easier than discrete logarithms, and they are much easier if you know the factorization of the group order. If you're dealing with a precomputed list of 32- or 64-bit ...
Ben Smith's user avatar
  • 864
11 votes

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

There is a vast literature on this subject of counter-examples to the Hasse principle. This local-to-global principle holds for quadratic forms and curves of genus $0$ (more generally for twisted ...
Chandan Singh Dalawat's user avatar
11 votes

Is the sum of digits of $3^{1000}$ divisible by $7$?

Middle digits of the numbers $3^n$ are unpredictable. At least it is too hard for current techniques to say anything about them. It means that the their sum is unpredictable as well. Some good random ...
Alexey Ustinov's user avatar
11 votes

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

You may use Faulhaber's formula $$ \sum_{k=1}^p k^{p-1}=\frac{p^p}p+\frac12 p^{p-1}+\sum_{k=2}^{p-1} \frac{B_k}{k!}\,(p-1)^{\underline{k-1}}\,p^{p-k}. $$ All summands except this corresponding to $k=...
Fedor Petrov's user avatar
11 votes

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

It is a theorem of Lerch of 1905. An elementary proof can be found in this article of Sondow : https://arxiv.org/abs/1110.3113
François Brunault's user avatar
11 votes

A conjecture about 433

Since $2$ has multiplicative order $72$ modulo $433$, it is easy to check with a quick computation that $2^{2n}-2^n+1\equiv 0\pmod{433}$ holds iff $n\equiv\pm 12\pmod{72}$, or $m\equiv\pm 3\pmod{18}$. ...
Wojowu's user avatar
  • 27.4k
10 votes

Probability in $GL_2(\mathbb{Z}/p^{r}\mathbb{Z})$

Total number of elements in $$\bigl|\mathrm{GL}_2(\mathbb{Z}/p^{r+1}\mathbb{Z})\bigr|=p^{4r}(p^2-1)(p^2-p).$$ Let us count the number of matrices with a given trace $s$. It is $$\sum_{a\in \mathbb{Z}/...
Fedor Petrov's user avatar
10 votes
Accepted

For which values of $k$ is it known that there are infinitely many $n$, such that $2^{n+k}\equiv 1\pmod{n}$?

For any $k\geq 1$, there are infinitely many solutions of the congruence $2^{n+k}\equiv 1\pmod{n}$. To see this, observe first that there is always a solution $n\geq 1$ satisfying $n+k\geq 7$. Indeed, ...
GH from MO's user avatar
  • 101k
10 votes

A conjecture on binomial coefficients and roots of unity

Here is an elementary and explicit way to see this: Suppose we have a set of $p$ integers $A=\{a_1, a_2,\dots, a_p\}$ which forms a complete set of residues modulo p. Then we have $$\prod_{a\in A}(x-a)...
Gjergji Zaimi's user avatar
9 votes
Accepted

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

Your question is entirely answered and with a lot of additional detail by Corollary 11.4.2 of my book Springer Graduate Texts in Math GTM 240. This must be in the literature outside of my book, but I ...
Henri Cohen's user avatar
  • 11.9k
9 votes
Accepted

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

Let $u_n = a s_n + b t_n + c s_{n+1}$. The stronger claim is true: for large enough values of $n$, the number $u_n$ will be exactly divisible by a fixed power of $2$ that doesn't depend on $n$. Let $...
user172190's user avatar
9 votes

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$?

No, for $n = 11$ this fails: 363 = 3 * 11^2 with [7, 2, 8, 5, 3, 4, 6, 9, 10, 1, 11] 484 = 2^2 * 11^2 with [10, 9, 6, 3, 1, 2, 4, 5, 7, 8, 11] Running the code I wrote to check this a little more, ...
Moritz Firsching's user avatar
8 votes

For which values of $k$ is it known that there are infinitely many $n$, such that $2^{n+k}\equiv 1\pmod{n}$?

Sorry, this is in fact trivial. For instance if $2^{n+1}\equiv1\pmod{n}$ then $n$ is of course odd, so $2^{3n+3}\equiv1\pmod{n}$ and mod $3$, so $2^{3n+3}\equiv1\pmod{3n}$. This probably works for all ...
Henri Cohen's user avatar
  • 11.9k
8 votes

Is the sum of digits of $3^{1000}$ divisible by $7$?

Not an answer, but a series of considerations. One expects not only the digit sum of 3^n to be a multiple of nine (for integral n greater than 1) but also for the string of digits (in the decimal ...
Gerhard Paseman's user avatar
8 votes
Accepted

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

The answer is affirmative when $(p,n)$=1, even without the assumption that $p$ is a prime. Let us fix $p$ and proceed by induction on $n$. We can assume, without loss of generality, that $p\geq 2$. ...
GH from MO's user avatar
  • 101k
8 votes

Non-torsion part of the abelianisation of congruence subgroups

Suppose $r \geq 3$. Then one can show that $\Gamma=\mathrm{SL}(r,A)$ is a lattice in the group $G=\mathrm{SL}\big(r, {\mathbb F}_q(\!(1/t)\!)\big)$. The group $G$ has Kazhdan's property T and hence $\...
Venkataramana's user avatar
8 votes

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

The conjectures are true, and can be recovered from the action of $({\bf Z} / n {\bf Z})^2$ on $S_n$ by composition from the right and left with translations $k \mapsto k + a \bmod n$. Translation by ...
Noam D. Elkies's user avatar
8 votes

Reversing the CRT: Is $5$ tough?

The system of congruences in question is equivalent to $2^{pq}\equiv 2x\pmod{pq}$, i.e., the question is whether there exists an odd semiprime solution $n$ to $2^n\equiv c\pmod{n}$ (where $c=2x$). ...
Max Alekseyev's user avatar
8 votes

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?

Yes. In fact, you can take $n=1$. Let $g = \sum_{i=0}^d g_i$ with $g_i$ homogeneous of degree $i$. Then $$ \begin{aligned} g^2 &= \bigg( \sum_{k=0}^{ \lfloor d/2\rfloor} g_{d-2k} + \sum_{k=0}^{ \...
Will Sawin's user avatar
  • 138k
7 votes

Harmonic congruence

Let's use the fact that $$\frac{1}{j}\equiv \frac{(-1)^{j-1}}{p}\binom{p}{j}\pmod{p}$$ to rewrite your sum mod p as $$\sum_{j=1}^{p-1}\frac{(-1)^{\frac{(j+2)(j-1)}{2}}}{p}\binom{p}{j}=\frac{1}{p}\...
Gjergji Zaimi's user avatar
7 votes

Solutions to nonhomogeneous quadratic equation mod $N$

In order to get solutions of the congruence you are interested in let us consider the equation $x^2+y^2-x-Nz=0$. Using the trivial solution $x=1, y=0, z=0$, we parametrize all rational solutions by ...
Maciej Ulas's user avatar
7 votes

Could a nice principle be extracted from this lemma of Gauss

In response to your second query "An alternative proof would be also welcome": A (nearly) one-page proof of a stronger version ($q<\sqrt p$ instead of $q<p$)$^\ast$ is lemma 5.6 in ...
Carlo Beenakker's user avatar
7 votes
Accepted

Binomial coefficient congruence modulo $p^n$

This is false in general. To show this, I will use the congruence $$ \binom{p^k a}{p^k b} \equiv \binom{p^{k-1} a}{p^{k-1}b} \bmod p^{3k}$$ for $p\ge 5$ and $k \ge 1$. This is originally due to ...
Ofir Gorodetsky's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible