Register to reply

Number Theory

by popitar
Tags: number theory
Share this thread:
popitar
#1
Feb4-11, 06:25 PM
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.
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
al-mahed
#2
Feb4-11, 06:47 PM
P: 258
you may want to check [tex]\varphi{([n-1]^2)}[/tex]
popitar
#3
Feb4-11, 06:56 PM
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.

popitar
#4
Feb4-11, 06:58 PM
P: 17
Number Theory

Quote Quote by al-mahed View Post
you may want to check [tex]\varphi{([n-1]^2)}[/tex]
How do I check it?
al-mahed
#5
Feb4-11, 10:35 PM
P: 258
Quote Quote by popitar View Post
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]
popitar
#6
Feb4-11, 10:36 PM
P: 17
Thank you! But at this moment we didnt study anything about Phi function. Do you know any other method?
al-mahed
#7
Feb5-11, 10:59 AM
P: 258
Quote Quote by al-mahed View Post

(...)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?
popitar
#8
Feb5-11, 11:13 AM
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..
al-mahed
#9
Feb5-11, 11:37 AM
P: 258
Quote Quote by popitar View Post
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 ?
popitar
#10
Feb5-11, 11:40 AM
P: 17
I believe k elements.
al-mahed
#11
Feb5-11, 11:53 AM
P: 258
Quote Quote by popitar View Post
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
popitar
#12
Feb5-11, 12:14 PM
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
popitar
#13
Feb5-11, 12:22 PM
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
al-mahed
#14
Feb5-11, 12:43 PM
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
popitar
#15
Feb5-11, 12:55 PM
P: 17
Can you explain this part :(a+1)^[k-1]+(a+1)^[k-2]+...+(a+1)+1 = a*S + k?
popitar
#16
Feb5-11, 01:04 PM
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!
popitar
#17
Feb5-11, 01:41 PM
P: 17
Prove that a divides bc if and only if a/(gcd(a,b)) divides b.
popitar
#18
Feb5-11, 02:42 PM
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.


Register to reply

Related Discussions
Number Theory: Calculating mod large number Calculus & Beyond Homework 9
Number Theory Calculus & Beyond Homework 4
Measure theory and number theory? Linear & Abstract Algebra 18
Division theory..and Prime Number theory.. Linear & Abstract Algebra 3