0
$\begingroup$

Let a,b $\in$ $\mathbb{Z}$. Obviously, a counterexample can disprove this statement.
I tried this approach to seek another method (possibly proof by contradiction):

$a|b!$
$a|[b(b-1)!]$

If $gcd(a,(b-1)!)=1$, then $a|b$ and hence: $a \le b$.
But I think claiming that $a|b$ is too restrictive because $a$ can be less than $b$ without having $a|b$ necessarily.


I tried to study two cases to reach a contradiction that $gcd(a,(b-1)!)\not=1$, yet I couldn't figure out how to continue so this might actually help out :
1) $a=b$
2) $a \lt b$


Is there any mistake that I have done? Is this proof inconclusive or are there any improvements to be made so that it is a valid proof?
Thank you in advance
EDIT: Counterexamples most certainly get the job done here. Though, I am seeking another method to disprove the statement.
EDIT 2: The original proposition is: $$a \le b \Rightarrow b! \equiv 0 \pmod a$$
I am trying to justify whether the converse of this statement is right or wrong, which is obviously wrong using counterexamples. The purpose is to find another method to disprove the converse.

$\endgroup$
3
  • $\begingroup$ Without further restrictions this is false big time, for exmple: $\;-7=0\pmod 7\;$ , yet $\;-7<7\;$ ...This is specially important as we usually work within $\;\Bbb Z\;$ when doing this kind of problems... $\endgroup$
    – DonAntonio
    Jun 8, 2020 at 10:58
  • $\begingroup$ Please refrain from making minor edits. Also, please take a look at the description of the tag proof-writing before adding it. $\endgroup$
    – Ѕааԁ
    Jun 13, 2020 at 14:37
  • $\begingroup$ Thank you for the note. The tag wiki states that:" I have written the following proof, could I somehow improve it, does it have good flow/can I improve readability? ", and i think my question was kind of similar $\endgroup$ Jun 13, 2020 at 14:53

2 Answers 2

3
$\begingroup$

I think there's no point to try and prove a false statement. Because $15|5!$ for example.

What is a true version of this statement is $$a|b! \implies \text{prime factors of }a \le b$$ You can try and prove this!

Update: I understood you seek to prove it without using counterexamples, so let's try:

Let $p$ and $q$ be prime numbers where $p > q$, we have $pq|p!$ while $pq >p$

Another update: in your solution of "disproving the statement" you suggested that $\gcd(a,(b-1)!)=1$ while $a \le b$. Well if $a<b$ we have $a|(b-1)!$ so this directly means $a=b$ and this is something you wouldn't want as a step in disproving the statement. So the thing you'd first try is finding $a>b$ and $a|b!$, and I've given that in my first update.

$\endgroup$
5
  • $\begingroup$ You are right that it is pointless, but I am trying to disprove it without using counterexamples. Appreciate your recommendation though! $\endgroup$ Jun 8, 2020 at 11:32
  • $\begingroup$ @OmarS Oh, I didn't notice. I will try and edit and answer for that $\endgroup$ Jun 8, 2020 at 11:36
  • $\begingroup$ @OmarS Is that ok? I think disproving a theorem doesn't require formality and cases and stuff like that. It just requires a case at which the statement doesn't work. It does work for some integers but not for all, I suggest you look closely and explain clearly what exactly you need from such a problem/proof $\endgroup$ Jun 8, 2020 at 11:39
  • $\begingroup$ Perhaps you are right, i should have included what i needed exactly. I will edit the post and thank you for the head's up! $\endgroup$ Jun 8, 2020 at 12:55
  • $\begingroup$ The second update is exactly what i needed. $a > b$ to be exact. I will work on it and post an updated answer. Thank you for your efforts $\endgroup$ Jun 8, 2020 at 15:55
2
$\begingroup$

$b = 5$ and $a = 6$ is a counterexample.

The statement is true, however, if $a$ is further assumed to be prime.

Note that $b!$ has as factors, all natural numbers $\le b$. If $a$ is prime and $a > b$, then $a$ cannot divide $b!$ since $a$ is a prime factor of $a$ that won't divide $b!$.

If $a$ is not prime, then it is possible for all of its prime factors (with appropriate multiplicities) to be factors of $b!$ even if $b < a$, as shown above.

$\endgroup$

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.