1
$\begingroup$

This is one of my question from my Discrete Mathematics tutorial as well as its solution. I’m having trouble deciphering why the algorithm works using my propositional logic. Here is the question and solution.

Note that $a \vert b$ implies a divides b here, if the notation is not standardised.

Question: Find a positive integer n such that:

(i) its prime factorization contains no repeated prime factors; and

(ii) for any prime p, $p \vert n \iff (p − 1) \vert n$.

Be sure to clearly explain and justify how you obtain n.

Solution:

  1. Let S be the multiset (ie. duplicates allowed) of prime factors of n. (We seek to determine all the members of S.)
  2. By the unique prime factorization theorem, we may list the primes in S from smallest to largest: $p_{1}, p_{2}, . . . , p_{k}$, for some $k \in \Bbb Z^{+}$.
  3. By Property (i), this list is distinct, ie. $p_{i} \neq p_{j}$ for all $i,j \in 1,2,...k$.
  4. Property (ii) implies that a prime p is in S if the prime factors of (p − 1) are also in S.

  5. This means that every prime p (except 2) in S may be written as 1 + the product of some of the distinct primes in S which are smaller than p.

  6. This gives us a way to determine the primes in S:
  7. Clearly,$2 \in S$ because $1\vert n$ and $1+1 = 2$ is prime.
  8. UsingLine5.,thismeans3∈S,because3=1+2,and2∈Sand3isprime.
  9. Using Line 5. again, this means $7 \in S$, because $7 = 1+2·3$ and both $2,3 \in S$ and $7$ is prime.
  10. UsingLine5.yet again,this means $43 \in S$,because $43=1+2·3·7$,and $2,3,7 \in S$ and $43$ is prime.
  11. No other primes are in S, because this process of writing a prime as 1 + product of some smaller primes stops after 43. For example, $2 · 3 · 7 · 43 + 1 = 1807 = 13 · 139$ is not a prime; $2 · 7 + 1 = 15$ is not a prime; $3 · 7 + 1 = 22$ is not a prime. By exhaustive checking, no other primes can be generated in this manner from $2, 3, 7, 43$.
  12. No other primes are in S because they cannot satisfy both Properties (i) and (ii).
  13. Hence $n=2·3·7·43=1806$. Note that $n = 6$ is not a solution. Because if it were, then clearly $6 \vert 6$, and thus by property (ii), we may let $p−1 = 6$, so that $p = 7$ which is prime, and thus $7$ must divide n, which is absurd. Likewise $42$ is not a solution.

What I usually do when learning proofs is write it as proposition logic and find out what structure is the most appropriate, trying to fit definitions and get newer results using transitivity. However, this doesn’t seem to work for algorithms. I actually have 2 issues with this question.

I understand that we can keep generating the next factor that belongs in $S$ using the backward direction of (ii) and also stop it the same way, by letting it remain a true/vaguously true statement(as what the last part of the explanation is saying). Since $n \vert n+1$ , the only way to ensure this is so is when the testing number, $n+1$ is not a prime number, so that the false hypothesis causes the statement to remain true.

a)However, I do not know a way to formerly explain why line 4 and line 5 are true. It seems that the forward direction of statement (ii) will fit in here.

I'm thinking about a statement introduced in class: 2 and 3 are the only primes whose difference is 1, which can be translated to $$\forall primes \ p,q, (p \gt q) \land (p-q=1) \to (p=3 \land q=2)$$, and this is logically equivalent to the proposition of $$\forall primes \ p,q, (p \gt q) \land (p-q=1) \land prime(p) \land \sim(p=3 \land q=2) \to \sim prime(q) $$, which shows some properties of the product, but I'm stuck here. Does this statement have any link to line 4 and 5?

b)Is there a general way to logically piece all these statements in propositional logic form? From what I see, is that they have translated (i) and (ii) to find $n$ using a bottom up approach of finding the factors, but it is surprising how the answers always write "exhaustive checking" or "trial and error", but I don't see a smart way to do it.

$\endgroup$
  • $\begingroup$ I would perhaps adjust your approach to proofs. Starting with the definitions is sensible, and allows you to deduce the logical consequences of them, but translating everything to propositional logic will surely do more harm than good? For me, mathematics is a creative art, and reducing it to propositional logic reduces your opportunities for creative thinking in your proof-sketching. $\endgroup$ – bounceback Sep 26 '18 at 16:41
  • $\begingroup$ terrytao.wordpress.com/career-advice/… $\endgroup$ – bounceback Sep 26 '18 at 16:42
  • $\begingroup$ @bounceback ok, do you by any chance know what's the logic behind line 4 and 5 then? $\endgroup$ – Prashin Jeevaganth Sep 26 '18 at 16:59
  • $\begingroup$ Think of an example, say $p = 5$. Property 2 and line 4 say that $5 \in S$ if and only if $2\times2 \in S$. Then line 5 is just saying we write $5 = 2\times2 +1$. $\endgroup$ – bounceback Sep 26 '18 at 17:04
  • $\begingroup$ @bounceback I mean is the implication in line 4 really clear enough without justification? $\endgroup$ – Prashin Jeevaganth Sep 26 '18 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.