4
$\begingroup$

While experimenting with modulo arithmetic I came upon this slight extension to Fermat's Little Theorem (for which I have a proof).

$$\text{If a is a positive integer and p is prime and }\ge\text{ 5 then}$$

$$a^p \equiv a\pmod{3\times p} $$

I cannot believe this has remained unnoticed but I will ask anyway.

Is there any chance this is new?

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ Is the proof too large to fit in the margins of the question box? $\endgroup$ – Oscar Lanzi Oct 5 '17 at 14:26
  • $\begingroup$ Actually, $a^p\equiv a\pmod{6p}$. $\endgroup$ – Thomas Andrews Oct 5 '17 at 15:12
  • 1
    $\begingroup$ More generally, if $p-1$ is divisible by $q-1$ for $p\neq q$ prime, then $a^p\equiv a\pmod{qp}$ $\endgroup$ – Thomas Andrews Oct 5 '17 at 15:20
  • $\begingroup$ Very special case of this generalized Fermat Euler Theorem. $\endgroup$ – Bill Dubuque Oct 10 '18 at 21:27
3
$\begingroup$

This is certainly known, but it doesn't have a name.

More generally,

Lemma: If $q$ is prime and $n$ is any positive integer such that $q-1\mid n-1$ then: $$a^n\equiv a\pmod{q}$$ Proof: This can be proved by induction on $k=\frac{n-1}{q-1}$.

Let $n_k=1+(q-1)k$. Then $n_0=1$ and $a^{1}\equiv a\pmod{q}$.

Now, if $a^{n_k}\equiv a\pmod{q}$, then $$a^{n_{k+1}}=a^{n_k}a^{q-1}\equiv a\cdot a^{q-1}=a^q\equiv a\pmod{q}$$

Now the case when $p\geq 5$ is prime and $q=3$ means $a^{p}-a$ is divisible by $p$ and $3$, thus, by $3p$.

It is also divisible by $2$, so you really get:

$$a^{p}\equiv a\pmod{6p}$$

You also have that if $p>5$ with $p\equiv 1\pmod 4$ then $a^p\equiv a\pmod{30p}$.

The lemma lets you assert, for example, that $a^{13}\equiv a\pmod{2\cdot 3\cdot 5\cdot 7\cdot 13}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks to everyone who replied, there is plenty for me to chew on here! $\endgroup$ – Robert G. Burns Oct 5 '17 at 15:36
4
$\begingroup$

Try these problem by yourself first: 1. Given relatively prime integers $a, b, c$, if I tell you any three numbers $i, j, k$, can you tell me an integer $N$ such that all three holds simontaneously: $$ N \equiv i \mod a$$ $$N \equiv j \mod b$$ $$N \equiv k \mod c$$ ? Can you always give me such $N$ ?

As a concrete example, can you tell me a number $N$ such that $$N \equiv 5 \mod 7$$ $$N \equiv 2 \mod 5$$ $$N \equiv 10 \mod 11$$ ?

Can you generalize ?

  1. When $N$ varies from $0$ to $5*7*11$, how does $$\{ N \mod 7 \}, \{ N \mod 5 \}, \{N \mod 11 \}$$ varies ?

Nice observation, but this is basically Chinese Remainder Theorem. (See the handout here for some nice and hard problems regarding this)

The $\mod p$ part is handled by Fermat's theorem, but the $\mod 3$ part is easily handled by observing $$ 2^{odd} \equiv 2 \mod 3$$ and $$1^{odd} \equiv 1 \mod 3$$.

In case you're feeling bad this turned out to be trivial, try this fun one if you didn't see it before: $2n$ divideds $\phi(a^n+1)$ for any integer $a, n$ with $gcd(a,n) = 1$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am sorry but don't understand why this is the Chinese Remainder Theorem (i'm not saying it isn't). Can I give an example in case my statement was imprecise? Take p dto be 7 and a to be 46, then 46 mod(21) is 4. Also 46^7 is 435817657216 and 435817657216 is 4 mod(21). And this is true for any a. $\endgroup$ – Robert G. Burns Oct 5 '17 at 14:51
  • $\begingroup$ @RobertG.Burns No problem $: )$. I have put two problems for you - try it by yourself and tell me the solutions in the comment after you've figured it out. If you still can't find the connection after thinking hardly, only then I will tell you $: )$ $\endgroup$ – cdt Oct 5 '17 at 14:54
1
$\begingroup$

Actually by Fermat's little theorem, $3$ always divides $$a^3-a=a(a^2-1)$$

As $p-1$ is even for $p\ge3$ $$a^{p-1}-1$$ is divisible by $a^2-1$

Hence, $a^p-a$ will be divisible by $3$ and $p$ and consequently by lcm$(3,p)$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So it's true but obvious? $\endgroup$ – Robert G. Burns Oct 5 '17 at 15:14
  • $\begingroup$ @RobertG.Burns, u r right $\endgroup$ – lab bhattacharjee Oct 5 '17 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.