estudier
Show that any number that is both square and cube (eg 64) is of form 7k or 7k +1
Delete
Share
This Question is Closed
lgbasallote
Best Response
You've already chosen the best response.
0
i assume we cannot consider 0
estudier
Best Response
You've already chosen the best response.
2
Humph...
estudier
Best Response
You've already chosen the best response.
2
Note that any number must be 7k + r with r = 0,1,...6
sauravshakya
Best Response
You've already chosen the best response.
1
@estudier i think all numbers can be expressed that way
cwrw238
Best Response
You've already chosen the best response.
0
(7k + r)^3 = (7k + r)^2
would that help - i'm clutching at straws to be honest!!
sauravshakya
Best Response
You've already chosen the best response.
1
So I think it is 7k+1
estudier
Best Response
You've already chosen the best response.
2
?
estudier
Best Response
You've already chosen the best response.
2
"(7k + r)^3 = (7k + r)^2"
Maybe expand these instead of setting them equal...
sauravshakya
Best Response
You've already chosen the best response.
1
1^6=7*0+1
2^6=7*9+1
3^6=7*104+1
4^6=7*585+1
I mean every number can be expressed as 7k + r with r = 0,1,...6
sauravshakya
Best Response
You've already chosen the best response.
1
So, I think u mean to say 7k+1
estudier
Best Response
You've already chosen the best response.
2
I mean every number can be expressed as 7k + r with r = 0,1,...6
Yes, I said that above....
sauravshakya
Best Response
You've already chosen the best response.
1
oh.....THAT WAS A HINT
estudier
Best Response
You've already chosen the best response.
2
The question does say 7k or 7k +1
NewbieCarrot
Best Response
You've already chosen the best response.
0
For 7k, (7k)^2 (mod 7)= 0^2 (mod 7)=0, (7k)^3 (mod 7)=0^3 (mod 7)=0
For 7k+1, (7k+1)^2 (mod 7)= 1^2 (mod 7)=1, (7k+1)^3 (mod 7)= 1^3 (mod 7)=1
For 7k+2, (7k+2)^2 (mod 7)= 2^2 (mod 7)=4, (7k+2)^3 (mod 7)= 2^3 (mod 7)=1
.........
For 7k+6, (7k+6)^2 (mod 7)= 6^2 (mod 7)=1, (7k+6)^3 (mod 7)= 6^3 (mod 7)=6
for any 7k+r, if the result is r, then it has the same form.
estudier
Best Response
You've already chosen the best response.
2
@NewbieCarrot Considering certain remainders is a good way to go....
sauravshakya
Best Response
You've already chosen the best response.
1
Well x=n^6...... Now, If n=0 MOD 7 then , n^6=0 MOD 7
Thus, x can be expressed as 7k.... Now if n=1,2,3,4,5,6 MOD 7
Then n^6=1 MOD 7 ---> BUT I HAVEN'T PROVED THIS PART.
estudier
Best Response
You've already chosen the best response.
2
(7k+r)^2 = 49k^2 + 14kr + r^2 = 7(7k^2+2kr) + r^2
estudier
Best Response
You've already chosen the best response.
2
(7k+r)^3 = 343k^3 +147k^2r +21kr^2 +r^3 =
7(49k^3 +21k^2r +3kr^2) +r^3
NewbieCarrot
Best Response
You've already chosen the best response.
0
@estudier You got it.
estudier
Best Response
You've already chosen the best response.
2
Not done yet....
NewbieCarrot
Best Response
You've already chosen the best response.
0
7(7k^2+2kr) + r^2
7(49k^3 +21k^2r +3kr^2) +r^3
have the same form with 7k+r while r=r^2=r^3 (mod 7)
estudier
Best Response
You've already chosen the best response.
2
OK, the reaminders are the same, and.....?
NewbieCarrot
Best Response
You've already chosen the best response.
0
The only possible answer is r=0 or 1. And we are done
sara12345
Best Response
You've already chosen the best response.
1
n = 7k+r
n^2 = 7x + r^2
n^3 = 7y + r^3
sara12345
Best Response
You've already chosen the best response.
1
r = [1,6]
estudier
Best Response
You've already chosen the best response.
2
"The only possible answer is r=0 or 1. And we are done"
True, but a little more explanation would be nice...:-)
sara12345
Best Response
You've already chosen the best response.
1
0 also
sara12345
Best Response
You've already chosen the best response.
1
let,n = 7k+r (r = 1,2,3,4,5,6)
n^2 = 7x + r^2
n^3 = 7y + r^3
plugin r = 1,2,3,4,5,6 and the intersection of remainders gives the form of a number thats both square and cube
estudier
Best Response
You've already chosen the best response.
2
Yes, that's right, well done.
estudier
Best Response
You've already chosen the best response.
2
Just include r= 0 as well....
sara12345
Best Response
You've already chosen the best response.
1
oh yes... .
sauravshakya
Best Response
You've already chosen the best response.
1
Is there this rule:
If n=x MOD y then, n^a = x^a MOD y
estudier
Best Response
You've already chosen the best response.
2
Is there this rule:
If n=x MOD y then, n^a = x^a MOD y
Yes (r>=1)
estudier
Best Response
You've already chosen the best response.
2
(a>=1)
sauravshakya
Best Response
You've already chosen the best response.
1
GREAT....... Then I think I proved if n=1,2,3,4,5,6 MOD 7 Then n^6=1 MOD 7
estudier
Best Response
You've already chosen the best response.
2
a^(p-1) = 1 mod p (gcd a,p = 1)
estudier
Best Response
You've already chosen the best response.
2
p prime
NewbieCarrot
Best Response
You've already chosen the best response.
0
Here is my experience, when you see this sentence "is of form 7k or 7k +1" you always should try all 7k+r to get the results. Same as 3k.
estudier
Best Response
You've already chosen the best response.
2
a^(p-1) = 1 mod p (p prime, gcd a,p = 1) (OR a^p = a mod p)
Fermat's Little Theorem
estudier
Best Response
You've already chosen the best response.
2
@sauravshakya
estudier
Best Response
You've already chosen the best response.
2
Indirectly related to the "necklace2 problem....
sauravshakya
Best Response
You've already chosen the best response.
1
WHAT!
sauravshakya
Best Response
You've already chosen the best response.
1
But how???? That is related to permutation and combination.
estudier
Best Response
You've already chosen the best response.
2
n^p-n strings involving 2 or more colours are partitioned into disjoint sets of p strings each set being strings obtained from each other by by a sequence of cycles ie p divides n^p-n which is Fermat's Little Theorem
estudier
Best Response
You've already chosen the best response.
2
Special case of your necklace problem....
Loads of beads of n colours, how many different necklaces of p beads can be made, p is prime?
estudier
Best Response
You've already chosen the best response.
2
(n^p-n)/2p + [n(p+1/2) -n]/2 + n
sauravshakya
Best Response
You've already chosen the best response.
1
Did u mean that every colour has only one bead.
estudier
Best Response
You've already chosen the best response.
2
You make a string of p beads and join the ends, so that's n^p strings.
Of those, n strings are beads of 1 colour alone (one for each colour)
So n^p-n strings having at least 2 colours etc etc....