Intereting Posts

Norms of linear maps
Finding integer cubes that are $2$ greater than a square, $x^3 = y^2 + 2$
Unbounded function on bounded interval not uniformly continuous
Lemma 1.3.4(b) in Bruns and Herzog
Computer software for solving mixed strategy Nash equilibrium
If $(A-\lambda{I})$ is $\lambda$-equivalent to $(B-\lambda{I})$ then $A$ is similar to $B$
Null space for $AA^{T}$ is the same as Null space for $A^{T}$
Is every ideal of $R$ a sum of a nilpotent ideal and an idempotent ideal?
Geometrico-Harmonic Progression
Complex prime numbers
Is linear algebra more “fully understood” than other maths disciplines?
polynomial values take on arbitrarily large prime factors?
Geometrical interpretation of $(\sum_{k=1}^n k)^2=\sum_{k=1}^n k^3$
Why $(\mathbb Q\times\mathbb Q)/(\mathbb Z\times{=})$ is not homeomorphic to $(\mathbb Q/\mathbb Z)\times(\mathbb Q/{=})$?
Find $\frac{\mathrm d^{100}}{\mathrm d x^{100}}\frac{x^2+1}{x^3-x}=$?

I can see that this works for any integer $n$, but I can’t figure out why this works, or why the number $42$ has this property.

- prove that $gcd(f_m, f_n) = f_{gcd(n, m)}$, where $f_n$ is the nth Fibonacci number.
- Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.
- Can an integer of the form $4n+3$ written as a sum of two squares?
- $n^5-n$ is divisible by $10$?
- How to solve for any given natural number n?
- Proof that the euler totient function is multiplicative, correctness?
- If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?
- Extended Euclidean Algorithm, what is our answer?
- Prove that $x^3 \equiv x \bmod 6$ for all integers $x$
- If $n\in\mathbb N$ and $k\in\mathbb Z$, solve $n^3-32n^2+n=k^2$.

Problems like this appear frequently here. There are a couple of standard approaches. One is to use Fermat’s little theorem, which says that if $p$ is a prime number, then $n^p-n$ is divisible by $p$ for all $n$.

Since $42=2\times 3\times 7$, what we need to do is to check that 2, 3, and 7 divide $n^7-n$, no matter what $n$ is.

That 7 does is direct from Fermat’s little theorem.

The theorem also ensures that 3 divides $n^3-n$. Now: $$n^7-n=n(n^6-1)=n((n^2)^3-1)=n(n^2-1)(n^4+n^2+1)=(n^3-n)(n^4+n^2+1),$$ so 3 indeed divides $n^7-n$.

Finally, $n$ and $n^7$ always have the same parity, so $n^7-n$ is even.

We can actually argue without Fermat’s little theorem in this case. An approach that only requires patience is as follows: The idea is to factor the polynomial $x^7-x$ and then analyze the result when $x=n$ is an integer. (This is a trick that Bill Dubuque suggests sometimes in his solutions.)

We have: $x^7-x=x(x^6-1)=x(x^3+1)(x^3-1)=x(x+1)(x^2-x+1)(x-1)(x^2+x+1)$. When $x=n$, we have

$$ n^7-n=(n-1)n(n+1)(n^2-n+1)(n^2+n+1). $$

Now we analyze this prime by prime, as before. Note that one of $n$ and $n-1$ is always even, so the product is even. Also, of 3 consecutive numbers, such as $n-1,n,n+1$, one is always divisible by 3, so it only remains to verify divisibility by 7.

We may assume that $n=7k+b$ where $b=\pm2$ or $\pm3$, since otherwise $(n-1)n(n+1)$ is a multiple of 7. In that case, $n^2\equiv 4$ or $2\pmod 7$, and one of $n^2+n$, $n^2-n$ is $\equiv 6\pmod 7$, so $(n^2-n+1)(n^2+n+1)$ is a multiple of 7.

The disadvantage of this approach over the previous one, of course, is the need to analyze different cases. Fermat’s little theorem allows us to analyze all cases simultaneously, which typically (as here) results in a much faster approach.

If you are comfortable with the method of induction, this gives us a way of verifying divisibility by 7 which is not without some elegance (divisibility by 2 and 3 is probably best approached as before). Note that $(-n)^7-(-n)=-(n^7-n)$, so we may as well assume that $n\ge 0$. If $n=0$ it is obvious that 7 divides $n^7-n$.

Suppose then that $7|n^7-n$, and argue that $7|(n+1)^7-(n+1)$. For this, actually expand $(n+1)^7$ using the binomial theorem: $$ (n+1)^7=n^7+7n^6+{7\choose 2}n^5+{7\choose 3}n^4+\dots+1.$$ The point is that $${7\choose k}=\frac{7!}{k!(7-k)!}$$ is obviously divisible by 7 as long as $k\ne0,7$, so (modulo 7) we have that $(n+1)^7-(n+1)\equiv (n^7+1)-(n+1)=(n^7-n)$. Now we invoke the induction hypothesis, that precisely says that the latter is divisible by 7, and we are done.

Of course, exactly the same inductive argument gives us a proof of Fermat’s little theorem: $p|n^p-n$ for any $p$ prime and any integer $n$.

It is a special case of the following global-form of little Fermat. $ $ For $\rm\, a,k,n\in\mathbb N$ with $\rm\ a,k > 1$

$\rm\qquad d\ |\ n^k\! -\! n\ $ for all $\rm\:n\:$ $\rm \iff\ d\:$ is squarefree, and $\rm\ p\!-\!1\ |\ k\!-\!1\ $ for all primes $\rm\:p\:|\:d$

Hence for $\rm\: a = 42 = 2\cdot 3\cdot 7\ $ we deduce: $\rm\ \ 42\ |\ n^k\!-n\ $ for all $\rm\:n \iff 6\ |\ k\!-\!1$

For the simple proof and further discussion see my 2009/04/10 sci.math post – which also presents the analogous generalization of Euler’s $\phi$ function, and Korselt’s criterion for Carmichael numbers. Note: to fix rotted Google Groups links in the cited sci.math post it may be necessary to change $\ $ http://google.com/… $\ $ to$\ $ http://groups.google.com/… i.e. insert “groups.” before “google.com”.

Here is another useful variation:

**Theorem** $\ \ \ n^{\large k+\phi}\equiv n^{\large k}\pmod{p^i q^j}\ \ $ assuming that $ \ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\, $ $\, i,j \le k,\,\ p\ne q.\ \ \ $

**Proof** $\ \, p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^{ \phi}\equiv 1\,\Rightarrow\, n^{k + \phi}\equiv n^k,\, $ by $\ n^{\Large \color{#0a0}\phi} = (n^{\color{#0a0}{\Large \phi(p^{ i})}})^{\large \color{#0a0}m}\!\overset{\color{blue}{\rm (E)}}\equiv\! 1^{\large m}\!\equiv\! 1$ by $\rm\color{blue}{E}$=Euler

$\qquad\quad\ \, \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^k\equiv 0\,\equiv\, n^{k + \phi}\ $ by $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{mp})^i$ and $\,k\ge i.$

So $\ p^i\mid n^{k+\phi}\!-n^k.\,$ By symmetry $\,q^j$ divides it too, so their lcm $ = p^iq^j\,$ divides it too. $\ $ **QED**

**Remark** $\ $ Obviously the proof immediately extends to an arbitrary number of primes. This leads the way to Carmichael’s Lambda function, a generalization of Euler’s phi function.

There are many equivalent ways of proving it.

First observe that $42$ divides a number iff $2,3$ and $7$ divides the number.

(Since $42 = 2 \times 3 \times 7$ and $\gcd(2,3) = \gcd(3,7) = \gcd(2,7) = 1$)

Divisibility by $2$:

Clearly, $2|(n^7-n)$ since $n^7$ and $n$ are of the same parity.

Equivalently you could argue out that $2|(n^2-n)$ directly from Fermat’s little Theorem. (This is an overkill of Fermat’s Little Theorem.)

Divisibility by $3$:

$n^7-n = n(n^6-1) = n(n^2-1)(n^4+n^2+1)=n(n+1)(n-1)(n^4+n^2+1)$.

$3|n$ or $3|(n-1)$ or $3|(n+1)$ and hence $3|(n^7-n)$.

Equivalently you could argue out that $3|(n^3-n)$ directly from Fermat’s little Theorem.

Divisibility by $7$:

Note that $n$ can be either $7k$ or $7k \pm 1$ or $7k \pm 2$ or $7k \pm 3$.

If $n=7k$ or $n=7k \pm 1$, we are again done since then $7|n$ or $7|(n+1)$ or $7|(n-1)$ and hence $7|(n^7-n)$.

If $n=7k \pm 2$, then $n^2 = (7k \pm 2)^2 = 7m + 4$ and $n^4 = (7m+4)^2 = 7l+2$.

Hence $n^4 + n^2 + 1 = 7l+2 + 7m + 4 + 1 = 7(l+m+1)$ and hence $7|(n^4 + n^2 + 1) \Rightarrow 7|(n^7-n)$.

If $n=7k \pm 3$, then $n^2 = (7k \pm 3)^2 = 7m + 2$ and $n^4 = (7m+2)^2 = 7l+4$.

Hence $n^4 + n^2 + 1 = 7l+4 + 7m + 2 + 1 = 7(l+m+1)$ and hence $7|(n^4 + n^2 + 1) \Rightarrow 7|(n^7-n)$.

Hence, $7|(n^7-n)$.

Equivalently you could argue out that $7|(n^7-n)$ directly from Fermat’s little Theorem.

Therefore, we have that $2|(n^7-n)$ and $3|(n^7-n)$ and $7|(n^7-n)$, $\forall n \in \mathbb{N}$.

Hence, $42|(n^7-n)$, $\forall n \in \mathbb{N}$.

As $42=2.3.7$. Therefore,we need to check that $n^7-n$ is divisible by $2,3$ and 7.

For divisibility by $2$, by fermat’s little theorem, $n^2=n\pmod 2 \implies {(n^2)}^3.n=n^4\pmod 2=n^2\pmod 2=n\pmod 2 \implies n^7-n=0\pmod2$.

For divisibility by 3, $n^3=n\pmod 3\implies n^7=n^3\pmod 3=n\pmod 3 \implies n^7-n=0\pmod 3$. For divisibility by 7, $n^7=n\pmod 7 \implies n^7-n=0\pmod 7$. These relations implies that $42|(n^7-n)$.

F$\ell$T$^*$ (if $p\not\vert n$, then $p\vert n^{p-1}-1$) $\Rightarrow$

if $2\not\vert n$, then $2\not\vert n^6$, and then $2\vert (n^6)^1-1$

if $3\not\vert n$, then $3\not\vert n^3$, and then $3\vert (n^3)^2-1=n^6-1$

if $7\not\vert n$, then $7\vert n^6-1$

so $2,3,7\vert n^7-n$.

$^*$: $\ell$=little.

Just for completeness, here is induction (just for divisibility by 7) :

Claim : $n^7 – n$ is divisible by 7

Base Case: True for n = 1,2

Induction Step:

Assume true for n = k. To prove true for n = k + 1.

Now, $$(k+1)^7 – (k+1) = k^7 + 7k^6 + 21k^5 + 35k^4 + 35k^3 + 21k^2 + 7k + 1 – k – 1 \\= (k^7 – k) + 7(k^6 + 3k^5 + 5k^4 + 5k^3 + 3k^2 + k)$$

We know by our assumption that $k^7 – k$ is divisible by 7. Therefore, $(k + 1)^7 – (k + 1)$ is divisible by 7.

This shows that $n^7 – n$ is divisible by 7.

To show divisibility by 2 and 3, unfortunately, one has to fall back on some of the earlier tricks.

$$n^7 – n = n(n^6 – 1) = (n-1)n(n+1)(n^2 – n + 1)(n^2 + n + 1)$$

$(n-1)n(n+1)$ is a product of three consecutive integers. Product of two consecutive integers is divisible by 2 and product of three consecutive integers is divisible by 3. Since, $(2,3) = 1$, product of three consecutive integers is divisible by 6. Since $(6,7) = 1$, $n^7 – n$ is divisible by 42.

QED

- Find minimum of $P=\frac{\sqrt{3(2x^2+2x+1)}}{3}+\frac{1}{\sqrt{2x^2+(3-\sqrt{3})x +3}}+\frac{1}{\sqrt{2x^2+(3+\sqrt{3})x +3}}$
- If two Borel measures coincide on all open sets, are they equal?
- Real Analysis, Folland Problem 5.3.29 The Baire Category Theorem
- Let $σ$ be the relation on $R×R$ in which $(a,b) σ (x,y)$ if and only if $a ≤ x$ and $b ≤ y$. Prove that $σ$ is a partial order relation.
- Hermitian Matrices are Diagonalizable
- Conformal map between annulii
- how to find integer solutions for $axy +bx + cy =d$?
- Can non-units be multiplied together to form units?
- Question about sets and classes
- Prove an analog of Rolle's theorem for several variables
- Importance of Cayley's theorem
- What is the inverse function of $\ x^2+x$?
- Example of two non-isomorphic fields which embed inside each other
- Proving by induction that $1^3 + 2^3 + 3^3 + \ldots + n^3 = \left^2$
- Proposition 5.21 in Atiyah-MacDonald