Prove that (n-1)^2 divides n^k -1

  • Thread starter popitar
  • Start date
  • #1
popitar
17
0
Let n>=2 and k>0 be integers. Prove that (n-1)^2 divides n^k -1 if and only if (n-1) divides k.
 

Answers and Replies

  • #2
al-mahed
262
0
you may want to check [tex]\varphi{([n-1]^2)}[/tex]
 
  • #3
popitar
17
0
I know that (n-1)^2 | (n^k-1) means that (n-1)^2 *m= (n-1)(n^[k-1]+n^[k-2]+...+n+1). But how do I connect this with (n-1)*a=k? Thanks.
 
  • #4
popitar
17
0
you may want to check [tex]\varphi{([n-1]^2)}[/tex]

How do I check it?
 
  • #5
al-mahed
262
0
How do I check it?

this is an implication "if and only if", <==>

I'll do the part <==, then you try to do the part ==>

prove that if n-1|k, then [tex](n-1)^2|n^k-1[/tex]:

proof:

first what is [tex]\varphi{([n-1]^2)}[/tex] ??

it is [tex](n-1)^{2-1}\cdot \varphi{(n-1)}=(n-1)\cdot \varphi{(n-1)}[/tex]

now, by euler, as [tex]gcd(n-1,\ n)=1[/tex] then

[tex]n^{\varphi{([n-1]^2)}}=n^{(n-1)\cdot \varphi{(n-1)}}\equiv\ 1\ mod\ (n-1)^2[/tex]

and by Lagrange we know that either [tex]k=(n-1)\cdot \varphi{(n-1)}[/tex] or [tex]wk=(n-1)\cdot \varphi{(n-1)}[/tex]

notice that [tex]\varphi{(n-1)}<n-1<k[/tex], and by hipothesis n-1|k

EDIT: conclusion is: therefore [tex]n^k\equiv\ 1\ mod\ (n-1)^2[/tex]
 
  • #6
popitar
17
0
Thank you! But at this moment we didnt study anything about Phi function. Do you know any other method?
 
  • #7
al-mahed
262
0
(...)and by Lagrange we know that either [tex]k=(n-1)\cdot \varphi{(n-1)}[/tex] or [tex]wk=(n-1)\cdot \varphi{(n-1)}[/tex]

oops, in fact it is

(...)and by Lagrange we know that either [tex]k=(n-1)\cdot \varphi{(n-1)}[/tex] or [tex]k=(n-1)\cdot \varphi{(n-1)}w[/tex]

popitar, try to rewrite and "play" with the equations you know related to it, factoring x^k-1 is a way, did your teacher give any similar problem with solutions?
 
  • #8
popitar
17
0
Thank you so much, Al-Mahed!
Factoring x^k - 1 is (x-1)(x^[k-1]+x^[k-2]+...+x+1), and I see that (x-1)^2 divides x^k-1means that (x-1) divides (x^[k-1]+x^[k-2]+...+x+1), but I don't see how I connect this with (x-1) divides k..
 
  • #9
al-mahed
262
0
Thank you so much, Al-Mahed!
Factoring x^k - 1 is (x-1)(x^[k-1]+x^[k-2]+...+x+1), and I see that (x-1)^2 divides x^k-1means that (x-1) divides (x^[k-1]+x^[k-2]+...+x+1), but I don't see how I connect this with (x-1) divides k..


how many elements you have in x^[k-1]+x^[k-2]+...+x+1 ?
 
  • #10
popitar
17
0
I believe k elements.
 
  • #11
al-mahed
262
0
I believe k elements.


correct, k elements, now you must show some work on it, grab a coffe (if you like) and think about it

hint: what means "x-1 divide k" in terms of euclidian form a=qb+r? how could you WRITE it down as an equation? and how to use it? you already saw by yourself you need to prove that x-1 divide x^[k-1]+x^[k-2]+...+x+1
 
  • #12
popitar
17
0
(x-1) divides k means (x-1) * p = k for some p positive integer. Then I multiply it by (x-1) I get the following (x-1)^2*p=k*(x-1). Then I can say that x^k-1 = k*(x-1)? But (x-1)*z=x^[k-1]+x^[k-2]+...+x+1.. ahh
 
  • #13
popitar
17
0
This is all I have
(x-1)^2 | x^k - 1 <=> (x-1)|k
(x-1)^2 * m = x^k -1 <=> (x-1)*z=k
(x-1)^2 *m = (x-1)(x^[k-1]+x^[k-2]+...+x+1) <=> (x-1)*z=k
(x-1)*m = x^[k-1]+x^[k-2]+...+x+1 <=> (x-1)*z=k
 
  • #14
al-mahed
262
0
write x-1=a, then k=ma=m(x-1) for some integer m, since x-1| k, it yields x=a+1

x^[k-1]+x^[k-2]+...+x+1 = (a+1)^[k-1]+(a+1)^[k-2]+...+(a+1)+1 = a*S + k=(x-1)S+m(x-1), since you'll have k 1's, and the rest of it multiplied by a
 
  • #15
popitar
17
0
Can you explain this part :(a+1)^[k-1]+(a+1)^[k-2]+...+(a+1)+1 = a*S + k?
 
  • #16
popitar
17
0
Ok. So you said I replace (x-1) by a, and x=a+1
(x-1)^2 | x^k - 1 <=> (x-1)|k
(x-1)^2 * m = x^k -1 <=> (x-1)*z=k
(x-1)^2 *m = (x-1)(x^[k-1]+x^[k-2]+...+x+1) <=> (x-1)*z=k
(x-1)*m = x^[k-1]+x^[k-2]+...+x+1 <=> (x-1)*z=k
a*m=(a+1)^[k-1]+(a+1)^[k-2] + ...+ (a+1)+1 <=> a*z=k
And from here what to do? Thanks!
 
  • #17
popitar
17
0
Prove that a divides bc if and only if a/(gcd(a,b)) divides b.
 
  • #18
popitar
17
0
We need to proofs:
1). If a|bc then a/d divides b, where d = gcd(a,b).
2). If a/d divides b then a|bc.
 
  • #19
al-mahed
262
0
Can you explain this part :(a+1)^[k-1]+(a+1)^[k-2]+...+(a+1)+1 = a*S + k?

Popitar, I'm not a teacher, I don't even have a major in mathematics, I'm just a curious guy, so you have to check all this stuff with your teacher.

Anyway, I think you are having trouble to understand the basic concepts of proof, but don't worry, you'll get it soon enough (it is quite confusing at the beginning).

You have to understand the binomial theorem, its expansion, to see that you'll have all the expression being divisible by a=x-1. So if a valid substitution yields a multiple of x-1 you're done in your demonstration that x-1 divide the expression, as required.

Now I think is a good idea turn out the internet and get pencil and paper... try to figure out some stuff by yourself now! Use a calculator to verify some ideas, you need to study more the basics, the euclidian algorithm is the most important thing right now.

That's the stuff you must study now in order to advance.


take care
 

Suggested for: Prove that (n-1)^2 divides n^k -1

Replies
4
Views
2K
Replies
7
Views
3K
Replies
2
Views
3K
Replies
29
Views
7K
  • Last Post
Replies
2
Views
916
Replies
7
Views
9K
Replies
1
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
3K
Top