mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)
-   -   Help with exercise questions from Elementary Number Theory (https://www.mersenneforum.org/showthread.php?t=27067)

 bur 2021-08-12 06:14

Help with exercise questions from Elementary Number Theory

I'm struggling with this problem:

[B]Show that the sum of the reciprocal of all primes [TEX]\frac{1}{p_{1}} + \frac{1}{p_{2}} + ... + \frac{1}{p_{n}} = P_{n}[/TEX] is never an integer.
[/B]

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:

[TEX]\frac{1}{p_{1}} + \frac{1}{p_{2}} + \frac{1}{p_{3}} = \frac{p_{1}*p_{2}+p_{1}*p_{3}+p_{2}*p_{3}}{primorial(p_{3})}[/TEX]

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?

[I](how do you produce a # in Tex here? \# or \text{#} didn't work...)[/I]

 axn 2021-08-12 06:53

[QUOTE=bur;585454]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.[/QUOTE]
This is not [B]quite[/B] correct. The important point is that p[SUB]i[/SUB] 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 p[SUB]i[/SUB], 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).

 sweety439 2021-08-12 10:33

[QUOTE=bur;585454]I'm struggling with this problem:

[B]Show that the sum of the reciprocal of all primes [TEX]\frac{1}{p_{1}} + \frac{1}{p_{2}} + ... + \frac{1}{p_{n}} = P_{n}[/TEX] is never an integer.
[/B]

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:

[TEX]\frac{1}{p_{1}} + \frac{1}{p_{2}} + \frac{1}{p_{3}} = \frac{p_{1}*p_{2}+p_{1}*p_{3}+p_{2}*p_{3}}{primorial(p_{3})}[/TEX]

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?

[I](how do you produce a # in Tex here? \# or \text{#} didn't work...)[/I][/QUOTE]

Since its denominator is always p1*p2*p3*...*pn and not 1

 Dr Sardonicus 2021-08-12 12:43

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"

$$H_{n}\;=\;\sum_{i=1}^{n}1/i$$

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 [i]numerator[/i] of the sum! We have the following well known result:

If p > 3 is prime, then H[sub]p-1[/sub] has a numerator divisible by p[sup]2[/sup] ["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.

 charybdis 2021-08-12 13:11

[QUOTE=Dr Sardonicus;585469]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 [i]numerator[/i] of the sum![/QUOTE]

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=bur;585454][I](how do you produce a # in Tex here? \# or \text{#} didn't work...)[/I][/QUOTE]

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\#}[/$$]

 MattcAnderson 2021-08-12 14:04

harmonic series

I seem to remember a Mathlogger Youtube video about infinite harmonic series.

Hope this Helps.

Matt

 bur 2021-08-13 13:56

Thanks for all the helpful replies!

One question though:[QUOTE]Since its denominator is always p1*p2*p3*...*pn and not 1[/QUOTE]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#.

 charybdis 2021-08-13 14:09

[QUOTE=bur;585570]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#.[/QUOTE]

Indeed. Maybe Sweety meant "the denominator when the fraction is written in lowest terms". But there was no attempt at a proof.

 Dobri 2021-08-14 01:22

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', [I]n[/I]#[I][sub]M[/sub][/I], for the product of the first [I]n[/I] Mersenne prime exponents.
For instance, 13#[I][sub]M[/sub][/I] = 2 × 3 × 5 × 7 × 13.
Also, [I]π[/I][I][sub]M[/sub][/I]([I]n[/I]) could be the Mersenne-prime-exponent-counting function, and [I]π[/I][I][sub]M[/sub][/I](13) = 5.

 bur 2021-08-26 06:30

[B]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.[/B]

Here's the next one where I'm struggling:

[I]Let p and p^2+8 be prime. Prove that p^3+4 is also prime.
[/I]
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?

 LaurV 2021-08-26 07:33

[QUOTE=bur;586538][B]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.[/B]
[/QUOTE]
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 :razz:)

 Dr Sardonicus 2021-08-26 15:54

[QUOTE=bur;586538]
[I]Let p and p^2+8 be prime. Prove that p^3+4 is also prime.
[/I]
<snip>
So only if p=3 we can have both p and p^2+8 be prime.
<snip>
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?[/QUOTE]
:tu: Yup.

 bur 2021-11-20 08:26

Another problem came up. The exercises deal with showing that a^x is congruent to 1 (or a) mod c, where c is a composite number:

a^21 == a (mod 15) for all a

This is not a problem yet, but what I'm struggling with is if the composite has the square of a prime, such as:

a^6 == 1 (mod 168) for all a where gcd(a,42)=1.

168 = 3*7*8 so it has to be shown that a^6 == 1 (mod 3), (mod 7), (mod 8). Mod 3 and 7 is no problem, but what about mod 8? 8 is not prime, so Fermat's little theorem cannot be applied. I noticed that apparently [TEX]a^{p^{n-1}(p-1)} \equiv 1 \pmod {p^{n}}[/TEX], but have no proof for it and I doubt they want that as solution as it wasn't discussed prior.

I could prove it by the fact that all odd numbers squared are == 1 (mod 8), so (a^3)^2 is as well, but that only works for mod 8. Also, a later question is:

a^4 = -1 (mod 60) for all a where gcd(a,30)=1.

So (mod 4=2^2) comes into it.

 Nick 2021-11-20 11:42

The square of every odd number is congruent to 1 (mod 8).

 Dr Sardonicus 2021-11-20 13:51

You could simply check a^2 (mod 8) for all four possible cases of a (mod 8). Then a^6 = (a^2)^3.

Note that knowing a^2 (mod 8) means you know a^2 (mod 4).

 R. Gerbicz 2021-11-20 16:37

[QUOTE=bur;593477]
This is not a problem yet, but what I'm struggling with is if the composite has the square of a prime, such as:

a^6 == 1 (mod 168) for all a where gcd(a,42)=1.

168 = 3*7*8 so it has to be shown that a^6 == 1 (mod 3), (mod 7), (mod 8). Mod 3 and 7 is no problem, but what about mod 8? 8 is not prime, so Fermat's little theorem cannot be applied. I noticed that apparently [TEX]a^{p^{n-1}(p-1)} \equiv 1 \pmod {p^{n}}[/TEX], but have no proof for it and I doubt they want that as solution as it wasn't discussed prior.[/QUOTE]

That is [url]https://en.wikipedia.org/wiki/Euler%27s_theorem[/url] for m=p^n. When you want the best exponent for all gcd(a,n)=1 it is also a known problem (n=168 in your case).

Let lambda(n)=lcm(,eulerphi(p[i]^e[i],) for n=prod(p[i]^e[i])
but if p=2 and e>2 then you can gain an additional factor of 2 on that place writing eulerphi(2^e)/2. And this is the best possible/smallest exponent what you can write for that a^lambda(n)==1 mod n for every gcd(a,n)=1.

For example in your case n=2^3*3*7 and lambda(n)=lcm(2,2,6)=6

ps. maybe in maths you're using the unmodified lcm() when p=2 and e>2, the ugly case here is due to the fact that there is no primitive root mod 2^e if e>2.The proof of the best exponent is easy: just use that there is a primitive root mod m iff m=1,2,4,p^e or 2*p^e when p is an odd prime.

 bur 2021-11-21 05:54

[QUOTE=Nick;593483]The square of every odd number is congruent to 1 (mod 8).[/QUOTE]
I know, I wrote just that... ;)

[QUOTE=Dr Sardonicus;593485]You could simply check a^2 (mod 8) for all four possible cases of a (mod 8). Then a^6 = (a^2)^3.

Note that knowing a^2 (mod 8) means you know a^2 (mod 4).[/QUOTE]I didn't think of that. But in that case it still only works for powers of 2 as factors.

[QUOTE]That is [URL]https://en.wikipedia.org/wiki/Euler%27s_theorem[/URL] for m=p^n[/QUOTE]Thanks, this is the answer to my question, but seeing it, I think it wasn't what the creators of the exercise had in mind since eulerphi is one chapter later.

So I assume they were after answers specific to that problem i.e. divisibility of of squares by 8 and 4. Thanks for your help everyone.

 bur 2021-11-26 14:32

And another one:

Show that [TEX]{p-1\choose k}\equiv -1^k \pmod p[/TEX]

It probably shouldn't use Wilson's theorem since that only comes in the next section in the book.

I tried to write it as a fraction:

[TEX]{p-1\choose k}=\frac{(p-k)\cdot...\cdot(p-1)}{k!}=\frac{(k+1)\cdot...\cdot(p-1)}{(p-1-k)!}[/TEX]

All those factors cannot be reduced (mod p) since they smaller than p. And $$p-1\equiv-1\pmod p$$.

I'd be thankful for a hint in the right direction.

 charybdis 2021-11-26 18:12

[QUOTE=bur;593946]I tried to write it as a fraction:

[TEX]{p-1\choose k}=\frac{(p-k)\cdot...\cdot(p-1)}{k!}=\frac{(k+1)\cdot...\cdot(p-1)}{(p-1-k)!}[/TEX]

All those factors cannot be reduced (mod p) since they smaller than p. And $$p-1\equiv-1\pmod p$$.[/QUOTE]

It depends what you mean by "reduced". Try subtracting p from all the factors of the numerator, so p-1 turns into -1, p-2 into -2 etc, and see what that gives you.

 R. Gerbicz 2021-11-26 19:49

[QUOTE=bur;593946]And another one:

Show that [TEX]{p-1\choose k}\equiv -1^k \pmod p[/TEX]

It probably shouldn't use Wilson's theorem since that only comes in the next section in the book.[/QUOTE]

I see where you could use Wilson theorem in the problem, though those solutions would be a little ugly. But really don't see what is in the next chapter and what you could/should use.
Solutions without Wilson:

the precise problem: binomial(p-1,k)==(-1)^k mod p for 0<=k<p.
the start was good, say if the answer is x then
((p-1)*(p-2)*...*(p-k))/k!==x mod p multiple by k!, you need:
(p-1)*(p-2)*...*(p-k)==x*k! mod p, but in the left side: p-i==(-i) mod p for every i integer, so
(-1)*(-2)*...*(-k)==x*k! mod p
k!*(-1)^k==x*k! mod p, we can divide by k!, since k! is not divisible by p, so k! is relative prime to p.
(-1)^k==x mod p, what was needed.

There is a one line solution here:
(p-1)*(p-2)*...*(p-k)/k!==(-1)*(-2)*...*(-k)/k!==(-1)^k*k!/k!==(-1)^k mod p [you need somewhat more knowledge to understand this].

 Dr Sardonicus 2021-11-27 15:16

[QUOTE=bur;593946]And another one:

Show that [TEX]{p-1\choose k}\equiv -1^k \pmod p[/TEX]
<snip>[/QUOTE]Clearly binomial(p-1,0) = 1 = (-1)^0, so it's true for k = 0. Simplify the ratio binomial(p-1,k+1)/binomial(p-1,k) [you wind up with one linear term in the numerator and one in the denominator]. Check that the numerator and denominator are non-zero for k = 0 to p-2, and are equal and opposite (mod p).

 R. Gerbicz 2021-11-27 16:10

[QUOTE=Dr Sardonicus;594023]Clearly binomial(p-1,0) = 1 = (-1)^0, so it's true for k = 0. Simplify the ratio binomial(p-1,k+1)/binomial(p-1,k) [you wind up with one linear term in the numerator and one in the denominator]. Check that the numerator and denominator are non-zero for k = 0 to p-2, and are equal and opposite (mod p).[/QUOTE]

Modified your idea, close to a pure combinatorial proof:

The k=0 case is trivial, so assume that 0<k<p,
it is known: binomial(p-1,k-1)+binomial(p-1,k)=binomial(p,k) [for here you don't need that p is prime]

furthermore: k*binomial(p,k)=p*binomial(p-1,k-1) is also true, here the right side is divisible by p, so
the left side also, but 0<k<p, hence binomial(p,k) is divisible by p.
From this binomial(p-1,k)==-binomial(p-1,k-1)==...==(-1)^k*binomial(p-1,0)==(-1)^k mod p, what we needed.

 charybdis 2021-11-27 16:32

[QUOTE=R. Gerbicz;594026]...furthermore: k*binomial(p,k)=p*binomial(p-1,k-1) is also true...[/QUOTE]

And we can do this combinatorially too: both are the way of choosing k elements from a set of p elements, where we label one of those k elements as "special".
We get k*binomial(p,k) by choosing the set of k elements and then picking the special element, and p*binomial(p-1,k-1) by first picking the special element and then choosing the other k-1 elements from the remaining p-1 elements of our set.

More famously, binomial(p-1,k-1)+binomial(p-1,k)=binomial(p,k) is easiest to see combinatorially: we partition the binomial(p,k) choices of k elements from the numbers {1,...,p} into two, depending on whether they contain 1 or not. binomial(p-1,k-1) is the number of choices containing 1, and binomial(p-1,k) is the number of choices not containing 1.

 Dr Sardonicus 2021-11-29 16:05

[QUOTE=R. Gerbicz;594026]Modified your idea, close to a pure combinatorial proof:

The k=0 case is trivial, so assume that 0<k<p,
it is known: binomial(p-1,k-1)+binomial(p-1,k)=binomial(p,k) [for here you don't need that p is prime]
<snip>[/QUOTE]Of course! And for 0 < k < p, $$\frac{p!}{k!(p-k)!}$$ clearly is divisible by p because the denominator is composed of factors less than p.

The result can be extended slightly. Since p divides binomial(p,k) for 0 < k < p when p is prime, we have the "freshman's dream" polynomial identity in [b]F[/b][sub]p[/sub][x,y]

$$(x\;+\;y)^{p}\;=\;x^{p}\;+\;y^{p}$$

Repeatedly raising to the p[sup]th[/sup] power, we see that in [b]F[/b][sub]p[/sub][x,y] for any positive integer n,

$$(x\;+\;y)^{p^{n}}\;=\;x^{p^{n}}\;+\;y^{p^{n}}$$

which shows that binomial(p[sup]n[/sup],k) is divisible by p for 0 < k < p[sup]n[/sup].

Then the above argument shows that for p prime and any positive integer n,

[TEX]{p^{n}-1\choose k}\equiv -1^k \;\pmod p[/TEX]

 MattcAnderson 2021-12-03 13:29

more of this

*smile*

 bur 2021-12-10 17:33

Thanks a lot for all the replies, it will take me while to get through all that.

By "reduced" I meant, there would be no smaller integer congruent to them mod p. I forgot about that smaller could also mean "negative".

 bur 2022-01-31 18:35

And another one:

An exercise deals with an integer a having order 3 mod p. And it is to be shown that a+1 has order 6 mod p.

As a hint they give: [TEX]a^2 + a + 1 \equiv 0 \pmod {p}[/TEX]. If I accept that, I can prove that a+1 will have order 6. But how do I get from [TEX]a^3 \equiv 1[/TEX] to [TEX]a^2 + a + 1 \equiv 0[/TEX]?

My problem is that I don't know what I can transform the a^3 into. [TEX]a^4 \equiv a[/TEX], but does that help? I also tried writing it as [TEX]a^3-1 = r*p[/TEX] which also didn't get me anywhere.

A small nudge in the right direction would be appreciated.

 charybdis 2022-01-31 19:35

Hint: how does a^3-1 factorize?

 R. Gerbicz 2022-02-01 11:41

[QUOTE=bur;599143]And another one:

An exercise deals with an integer a having order 3 mod p. And it is to be shown that a+1 has order 6 mod p.

As a hint they give: [TEX]a^2 + a + 1 \equiv 0 \pmod {p}[/TEX]. If I accept that, I can prove that a+1 will have order 6. But how do I get from [TEX]a^3 \equiv 1[/TEX] to [TEX]a^2 + a + 1 \equiv 0[/TEX]?[/QUOTE]

That is a wrong way and it is not even true: let a=1 (and p>3) then a^3=1 mod p but a^2+a+1 != 0 mod p.

The idea is only that, if you need just that order of (a+1) divides 6, then:

(a+1)^6==1 mod p, but that is true, because
a^2+a+1 | (a+1)^6-1 for every a integer, here a^2+a+1 is divisible by p, so (a+1)^6-1 is also divisible by p, hence (a+1)^6==1 mod p.

You need more, the order is 6, so it can't be 1,2 or 3 [we know that every "good exponent" is divisible by the order, so the order should divide 6]. If the order is odd, then:
(a+1)^3==1 mod p
in this case (a+1)^3-1-(a^2+a+1)*(a+2)=-2 but the left side is divisible by p, because (a+1)^3-1 and (a^2+a+1) is divisible by p.
This would mean that -2 is divisible by p, but p=2 can't be.

Now you need to handle only the order=2 case, so you can't have (a+1)^2==1 mod p. I left it for you.

 Dr Sardonicus 2022-02-01 12:24

[QUOTE=bur;599143]And another one:

An exercise deals with an integer a having order 3 mod p.
<snip>[/QUOTE]This means that a^3 == 1 (mod p) but a^1 =/= 1 (mod p); that is, a^3 - 1 == 0 (mod p) but a - 1 =/= 0 (mod p).

Supplementary exercise: If p is prime, n divides p-1, and a^n == 1 (mod p), then the order of a (mod p) is exactly n

if and only if a^d =/= 1 for any divisor d of n with n/d > 1.

Refinement: If and only if a^(n/q) =/= 1 (mod p) for every prime factor q of n

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