How many $n$-digit numbers composed solely of 0s and 1s are there with exactly $m$ "01" blocks?
Consider a number such as $X=0010111$. We can write between each of these digits the sign $=$ or $\neq$ indicating whether the two successive digits are equal or not. For our example, this would give $=\neq \neq \neq==$. The idea is that the blocks $« 01 »$ and blocks $« 10 »$ correspond to a sign $=$ and there is an alternation between «01» and «10». There are two issues here: first, we do not know the first digit, so we cannot reconstruct the original number, and second, if we have $m$ «01» blocks, we know there are either $m-1$, $m$, or $m+1$ «10» blocks, which does not give a fixed number of $\neq$ signs. The trick here is to add a digit 1 to the left of the number $X$ and a digit 0 to its right: 100101110. We then have the signs $\neq=\neq \neq \neq==\neq$. In this case, we can indeed reconstruct the number $X$, and since we start with a 1 and end with a 0, there is one more «10» block than «01» blocks. Therefore, there are $2m+1$ $\neq$ signs. The number now has $n+2$ digits, which gives $n+1$ $=$ or $\neq$ symbols. Finally, choosing $2m+1$ $\neq$ signs from the $n+1$ possible positions gives $\binom{n+1}{2m+1}$ possibilities.

## 8 Diophantine Equations, Factorization (Augustin & Éva)

## Course

A Diophantine equation is an equation whose solutions are integers. We generally have several unknowns raised to various integer powers. Unfortunately, there are no universal techniques or methods that work for all equations, but we can still highlight some basic approaches.

## Some Useful Factorizations:

$$
a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2} b^{1}+\ldots+b^{n-2} a^{1}+b^{n-1}\right)=\sum_{i}^{n-1} a^{n-1-i} b^{i}
$$

For $n$ odd:

$a^{n}+b^{n}=(a+b)\left(a^{n-1}-a^{n-2} b^{1}+\ldots-b^{n-2} a^{1}+b^{n-1}\right)=\sum_{i}^{n-1} a^{n-1-i}(-b)^{i}$

## Exercises

## Congruences

How to choose your modulo? We try to make sure that the powers give nice results, such as 1, meaning we will try to choose $p$ a prime number such that the powers in question divide or are multiples of $p-1$.

In particular, when we have many squares, we look modulo 4, 3, and 8 (in that order), and when we have cubes, we look modulo 9 and 7.