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)
\\\...

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

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

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

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

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

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

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

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

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

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

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

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

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}/...

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

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

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

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

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

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

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

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

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

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

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

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}^{ \...

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}\...

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

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

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

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

#### Related Tags

congruences × 131nt.number-theory × 100

prime-numbers × 21

co.combinatorics × 14

binomial-coefficients × 14

reference-request × 9

polynomials × 7

modular-forms × 7

diophantine-equations × 7

sequences-and-series × 6

algebraic-number-theory × 5

permutations × 5

computational-number-theory × 5

divisors-multiples × 5

analytic-number-theory × 4

algorithms × 4

finite-fields × 4

arithmetic-functions × 4

permanent × 4

quadratic-residues × 4

ag.algebraic-geometry × 3

gr.group-theory × 3

ac.commutative-algebra × 3

universal-algebra × 3

hypergeometric-functions × 3