Number Theory


by popitar
Tags: number theory
popitar
popitar is offline
#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
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
al-mahed
al-mahed is offline
#2
Feb4-11, 06:47 PM
P: 258
you may want to check [tex]\varphi{([n-1]^2)}[/tex]
popitar
popitar is offline
#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
popitar is offline
#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
al-mahed is offline
#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
popitar is offline
#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
al-mahed is offline
#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
popitar is offline
#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
al-mahed is offline
#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
popitar is offline
#10
Feb5-11, 11:40 AM
P: 17
I believe k elements.
al-mahed
al-mahed is offline
#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
popitar is offline
#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
popitar is offline
#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
al-mahed is offline
#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
popitar is offline
#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
popitar is offline
#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
popitar is offline
#17
Feb5-11, 01:41 PM
P: 17
Prove that a divides bc if and only if a/(gcd(a,b)) divides b.
popitar
popitar is offline
#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