mersenneforum.org Help with exercise questions from Elementary Number Theory
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2021-08-26, 15:54   #12
Dr Sardonicus

Feb 2017
Nowhere

14D616 Posts

Quote:
 Originally Posted by bur Let p and p^2+8 be prime. Prove that p^3+4 is also prime. So only if p=3 we can have both p and p^2+8 be prime. 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?
Yup.

Last fiddled with by Dr Sardonicus on 2021-08-26 at 15:56

 2021-11-20, 08:26 #13 bur     Aug 2020 79*6581e-4;3*2539e-3 22·7·17 Posts 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 $a^{p^{n-1}(p-1)} \equiv 1 \pmod {p^{n}}$, 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. Last fiddled with by bur on 2021-11-20 at 08:28
 2021-11-20, 11:42 #14 Nick     Dec 2012 The Netherlands 3·587 Posts The square of every odd number is congruent to 1 (mod 8).
 2021-11-20, 13:51 #15 Dr Sardonicus     Feb 2017 Nowhere 2×3×7×127 Posts 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).
2021-11-20, 16:37   #16
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×32×5×17 Posts

Quote:
 Originally Posted by bur 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 $a^{p^{n-1}(p-1)} \equiv 1 \pmod {p^{n}}$, but have no proof for it and I doubt they want that as solution as it wasn't discussed prior.
That is https://en.wikipedia.org/wiki/Euler%27s_theorem 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.

2021-11-21, 05:54   #17
bur

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

22·7·17 Posts

Quote:
 Originally Posted by Nick The square of every odd number is congruent to 1 (mod 8).
I know, I wrote just that... ;)

Quote:
 Originally Posted by Dr Sardonicus 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).
I didn't think of that. But in that case it still only works for powers of 2 as factors.

Quote:
 That is https://en.wikipedia.org/wiki/Euler%27s_theorem for m=p^n
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.

 2021-11-26, 14:32 #18 bur     Aug 2020 79*6581e-4;3*2539e-3 1DC16 Posts And another one: Show that ${p-1\choose k}\equiv -1^k \pmod p$ 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: ${p-1\choose k}=\frac{(p-k)\cdot...\cdot(p-1)}{k!}=\frac{(k+1)\cdot...\cdot(p-1)}{(p-1-k)!}$ 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.
2021-11-26, 18:12   #19
charybdis

Apr 2020

11×53 Posts

Quote:
 Originally Posted by bur I tried to write it as a fraction: ${p-1\choose k}=\frac{(p-k)\cdot...\cdot(p-1)}{k!}=\frac{(k+1)\cdot...\cdot(p-1)}{(p-1-k)!}$ All those factors cannot be reduced (mod p) since they smaller than p. And $p-1\equiv-1\pmod p$.
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.

2021-11-26, 19:49   #20
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×32×5×17 Posts

Quote:
 Originally Posted by bur And another one: Show that ${p-1\choose k}\equiv -1^k \pmod p$ It probably shouldn't use Wilson's theorem since that only comes in the next section in the book.
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.
Freely use whatever theorems are in your head.
Solutions without Wilson:

About this problem (I know tex but not writing Latex here to save time):
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].

Last fiddled with by R. Gerbicz on 2021-11-26 at 19:52 Reason: typo

2021-11-27, 15:16   #21
Dr Sardonicus

Feb 2017
Nowhere

533410 Posts

Quote:
 Originally Posted by bur And another one: Show that ${p-1\choose k}\equiv -1^k \pmod p$
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).

2021-11-27, 16:10   #22
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

27728 Posts

Quote:
 Originally Posted by Dr Sardonicus 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).
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.

 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 09:25.

Mon Jan 17 09:25:25 UTC 2022 up 178 days, 3:54, 0 users, load averages: 1.20, 1.04, 1.01

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

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.

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