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-11-27, 16:32   #23
charybdis

Apr 2020

35916 Posts

Quote:
 Originally Posted by R. Gerbicz ...furthermore: k*binomial(p,k)=p*binomial(p-1,k-1) is also true...
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.

Last fiddled with by charybdis on 2021-11-27 at 16:35

2021-11-29, 16:05   #24
Dr Sardonicus

Feb 2017
Nowhere

598810 Posts

Quote:
 Originally Posted by R. Gerbicz Modified your idea, close to a pure combinatorial proof: The k=0 case is trivial, so assume that 0
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 Fp[x,y]

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

Repeatedly raising to the pth power, we see that in Fp[x,y] for any positive integer n,

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

which shows that binomial(pn,k) is divisible by p for 0 < k < pn.

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

${p^{n}-1\choose k}\equiv -1^k \;\pmod p$

Last fiddled with by Dr Sardonicus on 2021-11-29 at 17:39 Reason: Omit repeated word

 2021-12-03, 13:29 #25 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 3·17·23 Posts more of this I am excited about this. *smile*
 2021-12-10, 17:33 #26 bur     Aug 2020 79*6581e-4;3*2539e-3 11318 Posts 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".
 2022-01-31, 18:35 #27 bur     Aug 2020 79*6581e-4;3*2539e-3 601 Posts 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: $a^2 + a + 1 \equiv 0 \pmod {p}$. If I accept that, I can prove that a+1 will have order 6. But how do I get from $a^3 \equiv 1$ to $a^2 + a + 1 \equiv 0$? My problem is that I don't know what I can transform the a^3 into. $a^4 \equiv a$, but does that help? I also tried writing it as $a^3-1 = r*p$ which also didn't get me anywhere. A small nudge in the right direction would be appreciated.
 2022-01-31, 19:35 #28 charybdis     Apr 2020 857 Posts Hint: how does a^3-1 factorize?
2022-02-01, 11:41   #29
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

30478 Posts

Quote:
 Originally Posted by bur 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: $a^2 + a + 1 \equiv 0 \pmod {p}$. If I accept that, I can prove that a+1 will have order 6. But how do I get from $a^3 \equiv 1$ to $a^2 + a + 1 \equiv 0$?
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.

2022-02-01, 12:24   #30
Dr Sardonicus

Feb 2017
Nowhere

22×3×499 Posts

Quote:
 Originally Posted by bur And another one: An exercise deals with an integer a having order 3 mod p.
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

 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 15:24.

Sat Oct 1 15:24:24 UTC 2022 up 44 days, 12:52, 1 user, load averages: 1.90, 2.30, 2.20

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.

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