# Number Theory

by popitar
Tags: number theory
 P: 17 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.
 P: 258 you may want to check $$\varphi{([n-1]^2)}$$
 P: 17 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.
P: 17

## Number Theory

 Quote by al-mahed you may want to check $$\varphi{([n-1]^2)}$$
How do I check it?
P: 258
 Quote by popitar 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 $$(n-1)^2|n^k-1$$:

proof:

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

it is $$(n-1)^{2-1}\cdot \varphi{(n-1)}=(n-1)\cdot \varphi{(n-1)}$$

now, by euler, as $$gcd(n-1,\ n)=1$$ then

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

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

notice that $$\varphi{(n-1)}<n-1<k$$, and by hipothesis n-1|k

EDIT: conclusion is: therefore $$n^k\equiv\ 1\ mod\ (n-1)^2$$
 P: 17 Thank you! But at this moment we didnt study anything about Phi function. Do you know any other method?
P: 258
 Quote by al-mahed (...)and by Lagrange we know that either $$k=(n-1)\cdot \varphi{(n-1)}$$ or $$wk=(n-1)\cdot \varphi{(n-1)}$$
oops, in fact it is

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

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?
 P: 17 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..
P: 258
 Quote by popitar 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 ?
 P: 17 I believe k elements.
P: 258
 Quote by popitar 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
 P: 17 (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
 P: 17 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
 P: 258 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
 P: 17 Can you explain this part :(a+1)^[k-1]+(a+1)^[k-2]+...+(a+1)+1 = a*S + k?
 P: 17 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!
 P: 17 Prove that a divides bc if and only if a/(gcd(a,b)) divides b.
 P: 17 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.

 Related Discussions Calculus & Beyond Homework 9 Calculus & Beyond Homework 4 Linear & Abstract Algebra 18 Linear & Abstract Algebra 3