Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Number Theory: Prove n divides 2^n - 2 if...?
Let p be a prime number with p > 3 and let n = (2^(2p) - 1)/3. Prove n|(2^n - 2).
Nice solution bboy! I'm going to leave this one open for another day or two in case others wish to post alternative solutions.
I'll post an alternative solution that uses the same idea as bboy's solution.
We want to show n|(2^n - 2) or 2^n = 2 (mod n). Employing wishful thinking, we can achieve this if we first show 2^(n-1) = 1 (mod n) or equivalently that n|(2^(n-1) - 1).
n - 1 = (2^(2p) - 4)/3 = (2^p - 2)(2^p + 2)/3 = 4(2^(p-1) - 1)(2^(p-1) + 1)/3. Notice that 3|(2^(p-1) - 1) since p-1 is even so 2^(p-1) - 1 is of the form 4^k - 1 = 0 (mod 3). Clearly 2|(n-1). Also observe that p|(2^(p-1) - 1) by Fermat's Little Thm which implies p|(n-1). Thus, 2p|(n-1).
Recall that we want to show
(2^(2p) - 1)/3 | (2^(n-1) - 1).
Note that if a, b are positive integers such that a|b, then x^b - 1 is divisible by x^a - 1 since we could express b in the form b = aj for some integer j, so x^b - 1 = x^(aj) - 1^j = (x^a)^j - 1^j = (x^a - 1)((x^a)^(j-1) + ... + 1).
Letting x = 2, a = 2p and b = n - 1 we get that (2^(2p) - 1) | (2^(n-1) - 1), so (2^(2p - 1)/3 | (2^(n-1) - 1) <--> n | (2^(n-1) - 1) as desired.
1 réponse
- jordanLv 4il y a 1 décennieRéponse favorite
First observe that 3 does not divide n since 9 does not divide 4^p-1; in fact ord_9 (4)=3 and p>3 is never a multiple of 3.
Obviusly n is odd.
let t a odd divisor of n (so it is >3), so 2^(2p) = 1 mod(t) so ord_(t){2}| (2p). we must show that 2^n=2 mod(t) iff 2^{n-1}=1 mod(t) iff 2^{(4^p-4)/3}=1 mod(t); but 4^p-4=4(4^{p-1}-1)=0 mod(2p) so ord_(t){2} | (2p) | 4^p-4, so we are done in fact it follows that 2^(n-1)=1 mod(n).
Nice question!
--
ok absird, don't worry, you have all time! :)
Source(s) : look my inequality,i assure it is very nice :)) http://it.answers.yahoo.com/question/index;_ylt=Ag...