Modular arithmetic and factorials

[Ciaran]

Hi there, I actually have a few questions I came across on my studies. They are
(a) Show that if p is odd and x is an integer such that x^2 ≡ 1 mod p^k, then x = ±1 mod p^k
(b) Find the solutions of the congruence equation x^2 ≡ 1 mod 2^k
(c) What is the remainder of (p − 1)!, when divided by p? In other words: find a simple
formula for (p − 1)! ∈ Zp.

I'm really not sure how to start a and b off, but for c I've been trying it with small examples, looking for a pattern.

Any help would be appreciated!

 

[Nono713]

For (a) and (b), try rewriting it as $x^2 - 1 \equiv 0 \pmod{p^k}$ and factor the LHS - what does that imply? For (c), think about what $(p - 1)!$ means: you're taking the product of all the integers from $1$ to $p - 1$. Think about modular inverses!

 

[Ciaran]

Thanks for your reply- I did factor the LHS and got (x+1)(x-1) and concluded that p cannot divide both factors? Not sure about the next step. For c, I thought making (p-1)! congruent to x mod p then multiplying through by p would work but I've ended up with 0 mod p= xp.

 

[Ciaran]

Ah, I have now solved a and b! But I am still not sure about c.

 

[Nono713]

Ah, I have now solved a and b! But I am still not sure about c.

Good job! For (c), consider that $x^2 \equiv 1 \pmod{p}$ if and only if $x$ is equal to its own modular inverse (e.g. divide through by $x$ to see that). That means that modulo $p$, only $1$ and $-1$ (which is equivalent to $p - 1$ modulo $p$) are their own inverses, and consequently you can partition the integers between $2$ and $p - 2$ into pairs of distinct modular inverses, and therefore... :p

 

[Ciaran]

Therefore the product 2x3... p-2 = p-2 ! is made up of these pairs?

 

[Nono713]

Yes, and since multiplication is commutative and each pair multiplies to 1 (since each integer in the pair is the inverse of the other) what does that tell you about the product $2 \times 3 \times \cdots \times (p - 2)$ modulo $p$? Perhaps more clearly, rearrange the product so that the pairs of inverses appear consecutively, what do you see?

Oh by the way I notice you didn't actually specify, $p$ is an odd prime in this context right? I am pretty sure it is but just making sure.

 

[Ciaran]

Yes- it is indeed an odd prime :) So (p-2)!= 1 mod p? Also, is this reason you added 'mod p' in the product because the inverses are only so in mod p?

 

[Nono713]

So (p-2)!= 1 mod p?

Yes, correct. As an example, take $p = 11$, so you have integers $2$ through $9$ to consider. Now let's see, the modular inverse of $2$ is $6$ since $2 \times 6 \equiv 12 \equiv 1 \pmod{11}$. The modular inverse of $3$ is $4$, the inverse of $4$ is $3$ (of course), the inverse of $5$ is $9$, the inverse of $6$ is $2$ (as seen before), and the inverse of $7$ Is $8$. At this point you have partitioned your set of integers (2, 3, 4, 5, 6, 7, 8, 9) into pairs of modular inverses (2, 6), (3, 4), (5, 9), (7, 8). Therefore we have:

$(11 - 2)! \equiv 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \equiv (2 \times 6) \times (3 \times 4) \times (5 \times 9) \times (7 \times 8) \equiv 1 \times 1 \times 1 \times 1 \equiv 1 \pmod{11}$

The same reasoning applies for any prime $p$, by using the properties of the modular inverse. Writing a rigorous proof for this is a nice exercise I think.

Now that you know what the remainder of $(p - 2)!$ modulo $p$ is, can you complete to find the remainder of $(p - 1)!$? What are the missing integers in the product?

Also, is this reason you added 'mod p' in the product because the inverses are only so in mod p?

Indeed, see more information at Modular multiplicative inverse - Wikipedia, the free encyclopedia, which explains modular inverses. They happen to be unique and behave much the same way as "normal" inverses like 3 and 1/3, except they are defined as integers modulo some other integer. Of course, if you haven't covered modular inverses yet you should want to prove some of its properties, which isn't too hard.

 

[Nono713]

You can also see that the argument breaks down if any integer is its own inverse, since we only get to multiply it once so it wouldn't cancel out with itself - this is why it's crucial to observe that the only integers that are their own inverses modulo a prime $p$ are $1$ and $-1$ (aka $p - 1$) as you've seen in the two previous questions, and handle these separately.

 

[Ciaran]

Could I just multiply throughout by p-1? so (p-2)!(p-1)= (p-1)(1 mod p) so (p-1)!= p mod p- 1 mod p= -1 mod p

 

[Nono713]

Could I just multiply throughout by p-1? so (p-2)!(p-1)= (p-1)(1 mod p) so (p-1)!= p mod p- 1 mod p= -1 mod p

Certainly, and that is correct! You have just found that the product of all integers from $1$ to $p - 1$ always leaves a remainder of $-1$ ($p - 1$) modulo $p$ when $p$ is prime

(also known as one half of Wilson's theorem)

 

[Ciaran]

That's truly beautiful. Thank you very much for all your help!