Question

What is the remainder when 70! is divided by 5183?

Answer 1

To say the truth, I have no idea where to start. Not a slightest.

Answer 2

have you heard of wilson's theorem before ?

Answer 3

Nope, checking it out right now.

Answer 4

No. Don't check it now. You should try to prove things based on your previous knowledge. Not new knowledge..

Answer 5

Maybe factor 5183 as a start

Answer 6

Oh, my, had to run the number through a program: 71 * 73

Answer 7

Remind me to teach you fermat's factorization later.
Its the best way to find a factor here

Answer 8

Noted it down. :)

Answer 9

I have figured out a way to solve this using below tools :
1) WIlson's theorem
2) Finding inverse of an integer in a given modulus
3) Chinese remainder theorem

Answer 10

Familiar with any of the above goodies ?

Answer 11

4) do the long division with
11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000
divided by 5183

Hey it's still possible :P

Answer 12

Have heard about chinese remainder theorem, but never used it and apart from its name I have no idea what it is. Others - no.
I guess I am going to look at all of them and learn like that. :)

Answer 13

I suggest you not to learn them on your own. It will be more efficient if somebody teaches them to you

Answer 14

Could you do that? ;)

Answer 15

I had to learn them on my own as I'm an engineer. I know how painful and unsettling it will be till you get the right idea

Answer 16

Okay good, lets start with wilson's theorem

Answer 17

Thank you very much! :)

Answer 18

Let me give you just the statement of wilson's theorem before getting into the detailed proof

Answer 19

Wilson's theorem :

\[(p-1)!\equiv -1\pmod{p}\]

whenever \(p\) is a prime

Answer 20

In other words \((p-1)!+1\) is divisible by \(p\) for every prime \(p\)

Answer 21

Okay, got it.

Answer 22

we will see why that must be true shortly
before that lets see a couple of quick examples

Answer 23

Is \((5-1)!+1\) divisible by \(5\) ?


Is \((7-1)!+1\) divisible by \(7\) ?

Answer 24

For both it is yes.

Answer 25

Good. Lets try and prove this

Answer 26

Well, it's because of Wilson's theorem. It states that (p - 1)! + 1 is divisible by p.
To check (4! + 1) / 5 = 25 / 5 = 5
(6! + 1) / 7 = 721/7 = 103

Answer 27

Nice. Before wilson's theorem, lets take a good look at inverses

Answer 28

Can you "guess" the value of x that satisfies the congruence ?
\[3x\equiv 1 \pmod{5}\]

Answer 29

well, (3x - 1)/5 must be integer, so we could construct an equation 3x - 1 = 5k So, one of the x's would be 2, then 7 and so on and on. But yeah, it's guessing.

Answer 30

Only integers allowed in modulus 5 are {0, 1, 2, 3, 4}

Answer 31

So, we can define THE inverse for every integers in any prime modulus

Answer 32

but for x we could take on bigger values, only the simplest form needs to satisfy the integers you gave, yes?

Answer 33

You may reduce every integer to one of {0, 1, 2, 3, 4} in modulus 5

Answer 34

Yes, got it.

Answer 35

So what is the inverse of 3 in modulus 5 ?

Answer 36

Would say that I have no idea what is inverse in this case.
But perhaps it's 2? Since it's the lowest integer satisfying 3x congruent to 1 (mod 5)?

Answer 37

Yes, 2 is the inverse of 3 in modulus 5

Answer 38

why ?

Answer 39

Multiplying 2 and 3 gives the multiplicative identity 1 in modulus 5.

So it does make sense to say that 3 is the inverse of 2 in modulus 5

Answer 40

Okay, got it.
So, for 3 in modulus 7 the multiplicative inverse would be 5?

Answer 41

Exactly!
whats the inverse of 5 in modulus 7 ?

Answer 42

3?

Answer 43

Yes. So you see that if \(a\) is the inverse of \(b\) in modulus \(n\),
then \(b\) is the inverse of \(a\) in modulus \(n\)

Answer 44

that simply follows from the commutative property of multiplication : \(ab=ba\)

Answer 45

Yes, got it.

Answer 46

Next consider the set of integers
\[\{0,1,2,\ldots,(p-1)\}\]
in modulus \(p\)

Answer 47

Yes.

Answer 48

Next consider the set of integers
\[\{1,2,…,(p−1)\}\]

in modulus \(p\)

Answer 49

I have removed 0 for a reason
it cannot have an inverse

Answer 50

Okay, got it.

Answer 51

Consider all other integers in prime modulus p

Answer 52

Lets prove below two facts about inverses in prime modulus p :
1) Every integer {1, 2, ..., (p-1)} has an inverse
2) The inverses are unique

Answer 53

In otherwords, we need to prove that below equation has an unique solution :
\[ax \equiv 1\pmod{p}\]

Answer 54

I have got no idea how to prove it.

Answer 55

where \(a\) is all integers that are not multiples of \(p\)

Answer 56

Could you push me into the right direction?

Answer 57

GCD(a, p) = 1
GCD(ax - 1, p) = not 1

Answer 58

Well, about how unique are inverses, perhaps we could say that they aren't unique. Then, let's multiply the set a by x (said inverse) and check, if all of the numbers mod (p) are congruent to 1. They wouldn't be. (A wall - why wouldn't they? I think I just did a circle around the problem)

Answer 59

Hey I need to go now. I suggest you go through below amazing book.
First 4 chapters cover everything you need to know to understand congruences and other advanced topics in number theory

http://www.zuj.edu.jo/?wpdmdl=12694&1534-D83A_1933715A=9aabfdad7763583bd2e5ba6dac4afa46586f9b55

Answer 60

will use == for congruency equal symbol:
xa = {xa_1, xa_2, ... , xa_(p -1)}
Lets say that xa_1 == 1 (mod p)
but since a_1 and a_2 are different values and a_2 isn't a multiplier of p, xa_2 won't satisfy xa_2 == 1 (mod p)

Answer 61

Okay! Thank you very much for all your help today!

Answer 62

Np. Do let me know if you figure out a simpler solution to the main problem

Answer 63

Okay ;) Have a great day!

Answer 64

@Kainui may have simpler ideas to solve the original main problem

Answer 65

Well I'm pretty sure I'm wrong about this but this is where I'm heading. Since this is a made up problem I kinda like to use that to my advantage since I'm thinking,

"OK 70! is the product of all number less than 71"

So to me since I am pretty sure 71 is probably prime, that should mean that all the numbers in 70! mod 71 have unique inverses and here they are all multiplied together by each other cancelling out to 1. I feel like this isn't completely true or useful, and at the very least it hints that 5183 might be divisible by 71, which we can quickly check to see it is, and that gets us \(5183 = 71*73\).

There are definitely some pieces here to pick up though, not sue where to take it from here since I'm looking at mod 71 not mod 5183.

Also, all the self-inverse numbers aren't multiplied by their inverses in 70! (if any exist). For example,

\[4! \equiv 1*2*3*4 \equiv 1*(2*3)*4 \equiv 1*1*(-1) \equiv -1\mod 5 \]

So not sure how to check for that sorta thing or what. I've definitely seen Wilson's theorem before , something to do with primes and factorials I think maybe I'll check that out again to see if I can remember it this time. Also I suspect the chinese remainder theorem might be useful cause I'm trying to look at separate things with the modulus a product... Might also be worth noting since 73 and 70 are so close it's also going to be quite simple possibly to evaluate 70! in mod 73...

Yeah, I suspect after looking at @ganeshie8 's comments that the mentions these things too so I probably am really on the same trail as him right now lol