Proof by Contradiction: Showing x <= n Leads to a Contradiction

[toothpaste666]

Homework Statement

lets say i have an int n that is greater than 2.
I know n!-1 = xk where x and k are integers I must show that x <= n leads to a contradiction

The Attempt at a Solution

i assume x = n
n!-1 =nk
(n-1)! -1/n = k
it seems to me that because of the 1/n k would not be an integer which would be a contradiction. But i am not even sure if that is true that it would not be an integer in any case. Am i going about this the right way?

 

[toothpaste666]

also x > 1

 

[toothpaste666]

and i also know x < n!

 

[toothpaste666]

wait so i have (n-1)! -k = 1/n
then (n-1)! - k is an integer because it is the sum and products of integers.
so int = 1/n
but n>2 so 1/n is not an int therefore there is a contradiction. is this correct?

 

[haruspex]

wait so i have (n-1)! -k = 1/n
then (n-1)! - k is an integer because it is the sum and products of integers.
so int = 1/n
but n>2 so 1/n is not an int therefore there is a contradiction. is this correct?

That's correct, but you've only proved it for x =n. You need to prove it for every 1 < x <= n.

 

[toothpaste666]

i was worried about that. I am not quite sure how to do this. I thought about doing it again for a n-1 but that also won't cover every case

 

[haruspex]

i was worried about that. I am not quite sure how to do this. I thought about doing it again for a n-1 but that also won't cover every case

That's right, you won't get there doing one at a time, but you can generalise your method so that it works for any x from 2 to n.

 

[toothpaste666]

I am not entirely sure how to do that. Can i say x is a particular but arbitrary integer from (2,n] and we have
int = 1/x
we know x is an int greater than 2 and there are no integers x greater than 2 such that 1/x is an integer therefore 1/x is not an int if 2 <x <= n
I am not sure how convincing this is though

 

[Dick]

If x is an integer in [2,n] then n!/x is an integer and xk/x is an integer and 1/x isn't. If that's what you meant, then it's convincing.

 

[toothpaste666]

i get up to n!/x is an integer because if x is between 2 and n then it will divide into one of the ints in n!. The rest I am not as confident. let me start back a few steps
n!-1 = xk
(n!-1)/x = k
n!/x-1/x = k
n!/x must be an int because x is a int from 2 to n so it cancels one of the ints in n! and then the rest will be an int because it is the product of ints.
n!/x - k = 1/x
now we have n!/x-k is an int because it is a sum of ints. this is a contradiction because we know that 1/x is not an int because x>2

 

[Dick]

i get up to n!/x is an integer because if x is between 2 and n then it will divide into one of the ints in n!. The rest I am not as confident. let me start back a few steps
n!-1 = xk
(n!-1)/x = k
n!/x-1/x = k
n!/x must be an int because x is a int from 2 to n so it cancels one of the ints in n! and then the rest will be an int because it is the product of ints.
n!/x - k = 1/x
now we have n!/x-k is an int because it is a sum of ints. this is a contradiction because we know that 1/x is not an int because x>2

Yes, 1/x is not an integer for x>=2. But as you've shown n!/x-k=1/x and the left side is an integer. That's a contradiction. So the assumption x<=n must be false.

 

[toothpaste666]

thank you