PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Low Entry average rating: No information on entry rating
Anton's congruence (Theorem)

For every $n \in \mathbb{N}$ $\pfac{n}$ stands for the product of numbers between $1$ and $n$ which are not divisible by a given prime $p$ . And we set $\pfac{0} =1$ .

The corollary below generalizes a result first found by Anton, Stickelberger, and Hensel:

Let $N_0$ be the least non-negative residue of $n \pmod{p^s}$ where $p$ is a prime number and $n \in \mathbb{N}$ . Then

$\displaystyle \left(n\underline{!}\right)_p \equiv \left(\pm 1\right)^{\left\lfloor n/p^s \right\rfloor}\cdot \left(N_0\underline{!}\right)_p \pmod{p^s}. $
Proof. We write each $r$ in the product below as $ip^s +j$ to get \begin{eqnarray*} \pfac{n} &=& \prod\limits_{\substack{1 \le r \le n\\ p^s \not\div r}} r \\ &=&\left( \prod\limits_{\substack{0 \le i \le \left\lfloor n/p^s\right\rfloor -1 \\ 1 \le j < p^s \\ p^s \not\div j}} ip^s +j\right)\left( \prod\limits_{\substack{i=\left\lfloor n/p^s\right\rfloor \\ 1\le j \le N_0 \\ p^s \not\div j}} ip^s +j\right) \\ &\equiv& \prod\limits_{i=0}^{\left\lfloor n/p^s \right\rfloor -1} \prod\limits_{\substack{1 \le j < p^s \\ p^s \not\div j }} j\cdot \prod\limits_{\substack{j=1 \\ p^s \not\div j}}^{N_0} j) \\ &\equiv& \pfac{p^s}^{\left\lfloor n/p^s\right\rfloor}\cdot \pfac{N_0} \pmod{p^s}. \end{eqnarray*}From Wilson's theorem for prime powers it follows that

\begin{displaymath} \left(n\underline{!}\right)_p \equiv \begin{cases} \left(N_0... ...erline{!}\right)_p & \text{otherwise.} \end{cases} \pmod{p^s}. \end{displaymath}
$ \qedsymbol$




"Anton's congruence" is owned by Thomas Heye.
(view preamble | get metadata)

View style:

See Also: factorial

Keywords:  relative prime

Attachments:
factorial modulo prime powers (Result) by Thomas Heye
Log in to rate this entry.
(view current ratings)

Cross-references: Wilson's theorem for prime powers, residue, prime, divisible, numbers, product
There are 2 references to this entry.

This is version 7 of Anton's congruence, born on 2003-01-23, modified 2004-04-01.
Object id is 3914, canonical name is AntonsCongruence.
Accessed 2420 times total.

Classification:
AMS MSC11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)