 mersenneforum.org Help with exercise questions from Elementary Number Theory
 Register FAQ Search Today's Posts Mark Forums Read  2021-08-12, 06:14 #1 bur   Aug 2020 79*6581e-4;3*2539e-3 659 Posts Help with exercise questions from Elementary Number Theory I'm struggling with this problem: Show that the sum of the reciprocal of all primes is never an integer. I know there are many solutions online, but at a quick glance they often give away the answer immediately or seem to take a different path, so I'd rather like a hint if my attempt is worthwhile: I came up with the general form of the fraction which has primorial pn# as denominator and the numerator is the sum of the products of all possible combinations of n-1 primes, i.e. "n choose n-1" addends. For example: A sum will never have a prime factor that isn't a prime factor of all addends. Since for all primes <= pn there is a addend that doesn't contain it, the sum, i.e. the numerator, will not be divisible by any of p1 ... pn. So it doesn't share any factor with the denominator. Thus, the fraction cannot be reduced to an integer. Is that reasoning correct? And if so, I guess the proof would have to contain a proof for why the fraction is of that form? (how do you produce a # in Tex here? \# or \text{#} didn't work...) Last fiddled with by LaurV on 2021-08-26 at 07:33   2021-08-12, 06:53   #2
axn

Jun 2003

2×2,719 Posts Quote:
 Originally Posted by bur A sum will never have a prime factor that isn't a prime factor of all addends. Since for all primes <= pn there is a addend that doesn't contain it, the sum, i.e. the numerator, will not be divisible by any of p1 ... pn.
This is not quite correct. The important point is that pi divides _all_ terms except for _one_. If more than one term was not divisible, you can't say anything about divisibility of the whole sum. But in this case, we know that everything else is divisible by pi, and therefore the whole is _not_ divisible.

Rest of the argument is fine, I think. You can't simplify that fraction any further (since none of the prime factors of the denominator appears in the numerator, by the above argument).   2021-08-12, 10:33   #3
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

2·7·263 Posts Quote:
 Originally Posted by bur I'm struggling with this problem: Show that the sum of the reciprocal of all primes is never an integer. I know there are many solutions online, but at a quick glance they often give away the answer immediately or seem to take a different path, so I'd rather like a hint if my attempt is worthwhile: I came up with the general form of the fraction which has primorial pn# as denominator and the numerator is the sum of the products of all possible combinations of n-1 primes, i.e. "n choose n-1" addends. For example: A sum will never have a prime factor that isn't a prime factor of all addends. Since for all primes <= pn there is a addend that doesn't contain it, the sum, i.e. the numerator, will not be divisible by any of p1 ... pn. So it doesn't share any factor with the denominator. Thus, the fraction cannot be reduced to an integer. Is that reasoning correct? And if so, I guess the proof would have to contain a proof for why the fraction is of that form? (how do you produce a # in Tex here? \# or \text{#} didn't work...)
Since its denominator is always p1*p2*p3*...*pn and not 1   2021-08-12, 12:43 #4 Dr Sardonicus   Feb 2017 Nowhere 34×7×11 Posts The fact that, for each prime p, only *one* of the fractions has a denominator divisible by p is indeed the key here. A slightly more sophisticated argument shows that for n > 1, the "harmonic numbers" all have denominators divisible by 2 - and, in fact, the power of 2 dividing the denominator never goes down, and increases every time n is a power of 2. The sum of fractions with a common factor in the denominator can be a fraction without that factor in the denominator, e.g. 1/3 + 1/6 = 1/2. In fact, the common factor can show up in the numerator of the sum! We have the following well known result: If p > 3 is prime, then Hp-1 has a numerator divisible by p2 ["Wolstenholme's Theorem"]. It follows that if p > 3 is prime, then 1/p + 1/(2*p) + ... + 1/((p-1)*p) has a numerator divisible by p.   2021-08-12, 13:11   #5
charybdis

Apr 2020

929 Posts Quote:
 Originally Posted by Dr Sardonicus The sum of fractions with a common factor in the denominator can be a fraction without that factor in the denominator, e.g. 1/3 + 1/6 = 1/2. In fact, the common factor can show up in the numerator of the sum!
This reminds me of another fun problem: show that every rational between 0 and 1 can be represented as the sum of reciprocals of distinct positive integers.

Quote:
 Originally Posted by bur (how do you produce a # in Tex here? \# or \text{#} didn't work...)
Like this: $$\#$$

Or like this:
$\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}=\frac{p_1p_2+p_1p_3+p_2p_3}{p_3\#}$   2021-08-12, 14:04 #6 MattcAnderson   "Matthew Anderson" Dec 2010 Oregon, USA 23×149 Posts harmonic series I seem to remember a Mathlogger Youtube video about infinite harmonic series. see https://www.youtube.com/watch?v=iJ8pnCO0nTY Hope this Helps. Matt   2021-08-13, 13:56   #7
bur

Aug 2020
79*6581e-4;3*2539e-3

659 Posts Thanks for all the helpful replies!

One question though:
Quote:
 Since its denominator is always p1*p2*p3*...*pn and not 1
Is that sufficient? 12/6 is an integer and the denominator is 2*3. The key would be to prove that it always remains 2*3 - or p#.   2021-08-13, 14:09   #8
charybdis

Apr 2020

929 Posts Quote:
 Originally Posted by bur One question though:Is that sufficient? 12/6 is an integer and the denominator is 2*3. The key would be to prove that it always remains 2*3 - or p#.
Indeed. Maybe Sweety meant "the denominator when the fraction is written in lowest terms". But there was no attempt at a proof.   2021-08-14, 01:22 #9 Dobri   "ม้าไฟ" May 2018 461 Posts The proof can be further simplified by noticing that the primorial (a term coined by Harvey Dubner) in the denominator is an even integer while the numerator is an odd integer. By the way, one could possibly use the term 'Mersennerial', n#M, for the product of the first n Mersenne prime exponents. For instance, 13#M = 2 × 3 × 5 × 7 × 13. Also, πM(n) could be the Mersenne-prime-exponent-counting function, and πM(13) = 5.   2021-08-26, 06:30 #10 bur   Aug 2020 79*6581e-4;3*2539e-3 659 Posts Could a mod change the thread titel to something like "Help with exercise questions from Elementary Number Theory"? So I don't have to open a new threads several times. Thanks. Here's the next one where I'm struggling: Let p and p^2+8 be prime. Prove that p^3+4 is also prime. As an initial remark: This is true for p=3 and then I couldn't find any other examples. Which is due to: (3k+1)^2+8 = 9k^2+6k+9 = 3(3k^2+2k+3) (3k+2)^2+8 = 9k^2+12k+12 = 3(3k^2+4k+4) So only if p=3 we can have both p and p^2+8 be prime. A bit weird way to phrase the question in that case, but the proof should still be possible, I guess? I thought about algebraic factors of p^3+4 or p^2+8, came as far as (p+2)(p-2)+12 = p^2+8. Other than that, no idea. Or is it really just about showing that it only holds for p=3 and since 3^3+4=31 is prime, that's the proof? Last fiddled with by bur on 2021-08-26 at 06:30   2021-08-26, 07:33   #11
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·23·149 Posts Quote:
 Originally Posted by bur Could a mod change the thread titel to something like "Help with exercise questions from Elementary Number Theory"? So I don't have to open a new threads several times. Thanks.
Done.

Related to your question, you just proved it, which is correct. What other proof do you want? (yes, the question is deliberately formulated in that tricky way, similar to "prove that if n-1 is a square and n+1 is a cube, then n-3, n+3, and n+5 are all prime", or the (in)famous "new mersenne conjecture", mathematicians have the right to joke too )

Last fiddled with by LaurV on 2021-08-26 at 07:40   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post jasong Miscellaneous Math 5 2016-04-24 03:40 mart_r Math 10 2009-04-05 07:29 mfgoode Puzzles 18 2007-07-13 18:03 AntonVrba Math 2 2006-09-20 17:20 gbvalor Math 1 2003-09-08 16:05

All times are UTC. The time now is 02:56.

Thu Feb 9 02:56:17 UTC 2023 up 175 days, 24 mins, 1 user, load averages: 0.58, 0.79, 0.83 This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔