Register to reply 
Number Theoryby popitar
Tags: number theory 
Share this thread: 
#1
Feb411, 06:25 PM

P: 17

Let n>=2 and k>0 be integers. Prove that (n1)^2 divides n^k 1 if and only if (n1) divides k.



#2
Feb411, 06:47 PM

P: 258

you may want to check [tex]\varphi{([n1]^2)}[/tex]



#3
Feb411, 06:56 PM

P: 17

I know that (n1)^2  (n^k1) means that (n1)^2 *m= (n1)(n^[k1]+n^[k2]+...+n+1). But how do I connect this with (n1)*a=k? Thanks.



#4
Feb411, 06:58 PM

P: 17

Number Theory



#5
Feb411, 10:35 PM

P: 258

I'll do the part <==, then you try to do the part ==> prove that if n1k, then [tex](n1)^2n^k1[/tex]: proof: first what is [tex]\varphi{([n1]^2)}[/tex] ?? it is [tex](n1)^{21}\cdot \varphi{(n1)}=(n1)\cdot \varphi{(n1)}[/tex] now, by euler, as [tex]gcd(n1,\ n)=1[/tex] then [tex]n^{\varphi{([n1]^2)}}=n^{(n1)\cdot \varphi{(n1)}}\equiv\ 1\ mod\ (n1)^2[/tex] and by Lagrange we know that either [tex]k=(n1)\cdot \varphi{(n1)}[/tex] or [tex]wk=(n1)\cdot \varphi{(n1)}[/tex] notice that [tex]\varphi{(n1)}<n1<k[/tex], and by hipothesis n1k EDIT: conclusion is: therefore [tex]n^k\equiv\ 1\ mod\ (n1)^2[/tex] 


#6
Feb411, 10:36 PM

P: 17

Thank you! But at this moment we didnt study anything about Phi function. Do you know any other method?



#7
Feb511, 10:59 AM

P: 258

(...)and by Lagrange we know that either [tex]k=(n1)\cdot \varphi{(n1)}[/tex] or [tex]k=(n1)\cdot \varphi{(n1)}w[/tex] popitar, try to rewrite and "play" with the equations you know related to it, factoring x^k1 is a way, did your teacher give any similar problem with solutions? 


#8
Feb511, 11:13 AM

P: 17

Thank you so much, AlMahed!
Factoring x^k  1 is (x1)(x^[k1]+x^[k2]+...+x+1), and I see that (x1)^2 divides x^k1means that (x1) divides (x^[k1]+x^[k2]+...+x+1), but I don't see how I connect this with (x1) divides k.. 


#9
Feb511, 11:37 AM

P: 258

how many elements you have in x^[k1]+x^[k2]+...+x+1 ? 


#10
Feb511, 11:40 AM

P: 17

I believe k elements.



#11
Feb511, 11:53 AM

P: 258

correct, k elements, now you must show some work on it, grab a coffe (if you like) and think about it hint: what means "x1 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 x1 divide x^[k1]+x^[k2]+...+x+1 


#12
Feb511, 12:14 PM

P: 17

(x1) divides k means (x1) * p = k for some p positive integer. Then I multiply it by (x1) I get the following (x1)^2*p=k*(x1). Then I can say that x^k1 = k*(x1)? But (x1)*z=x^[k1]+x^[k2]+...+x+1.. ahh



#13
Feb511, 12:22 PM

P: 17

This is all I have
(x1)^2  x^k  1 <=> (x1)k (x1)^2 * m = x^k 1 <=> (x1)*z=k (x1)^2 *m = (x1)(x^[k1]+x^[k2]+...+x+1) <=> (x1)*z=k (x1)*m = x^[k1]+x^[k2]+...+x+1 <=> (x1)*z=k 


#14
Feb511, 12:43 PM

P: 258

write x1=a, then k=ma=m(x1) for some integer m, since x1 k, it yields x=a+1
x^[k1]+x^[k2]+...+x+1 = (a+1)^[k1]+(a+1)^[k2]+...+(a+1)+1 = a*S + k=(x1)S+m(x1), since you'll have k 1's, and the rest of it multiplied by a 


#15
Feb511, 12:55 PM

P: 17

Can you explain this part :(a+1)^[k1]+(a+1)^[k2]+...+(a+1)+1 = a*S + k?



#16
Feb511, 01:04 PM

P: 17

Ok. So you said I replace (x1) by a, and x=a+1
(x1)^2  x^k  1 <=> (x1)k (x1)^2 * m = x^k 1 <=> (x1)*z=k (x1)^2 *m = (x1)(x^[k1]+x^[k2]+...+x+1) <=> (x1)*z=k (x1)*m = x^[k1]+x^[k2]+...+x+1 <=> (x1)*z=k a*m=(a+1)^[k1]+(a+1)^[k2] + ...+ (a+1)+1 <=> a*z=k And from here what to do? Thanks! 


#17
Feb511, 01:41 PM

P: 17

Prove that a divides bc if and only if a/(gcd(a,b)) divides b.



#18
Feb511, 02:42 PM

P: 17

We need to proofs:
1). If abc then a/d divides b, where d = gcd(a,b). 2). If a/d divides b then abc. 


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 