## estudier 3 years ago Show that any number that is both square and cube (eg 64) is of form 7k or 7k +1

1. lgbasallote

i assume we cannot consider 0

2. estudier

Humph...

3. estudier

Note that any number must be 7k + r with r = 0,1,...6

4. sauravshakya

@estudier i think all numbers can be expressed that way

5. cwrw238

(7k + r)^3 = (7k + r)^2 would that help - i'm clutching at straws to be honest!!

6. sauravshakya

So I think it is 7k+1

7. estudier

?

8. estudier

"(7k + r)^3 = (7k + r)^2" Maybe expand these instead of setting them equal...

9. sauravshakya

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

10. sauravshakya

So, I think u mean to say 7k+1

11. estudier

I mean every number can be expressed as 7k + r with r = 0,1,...6 Yes, I said that above....

12. sauravshakya

oh.....THAT WAS A HINT

13. estudier

The question does say 7k or 7k +1

14. NewbieCarrot

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.

15. estudier

@NewbieCarrot Considering certain remainders is a good way to go....

16. sauravshakya

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.

17. estudier

(7k+r)^2 = 49k^2 + 14kr + r^2 = 7(7k^2+2kr) + r^2

18. estudier

(7k+r)^3 = 343k^3 +147k^2r +21kr^2 +r^3 = 7(49k^3 +21k^2r +3kr^2) +r^3

19. NewbieCarrot

@estudier You got it.

20. estudier

Not done yet....

21. NewbieCarrot

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)

22. estudier

OK, the reaminders are the same, and.....?

23. NewbieCarrot

The only possible answer is r=0 or 1. And we are done

24. sara12345

n = 7k+r n^2 = 7x + r^2 n^3 = 7y + r^3

25. sara12345

r = [1,6]

26. estudier

"The only possible answer is r=0 or 1. And we are done" True, but a little more explanation would be nice...:-)

27. sara12345

0 also

28. sara12345

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

29. estudier

Yes, that's right, well done.

30. estudier

Just include r= 0 as well....

31. sara12345

oh yes... .

32. sauravshakya

Is there this rule: If n=x MOD y then, n^a = x^a MOD y

33. estudier

Is there this rule: If n=x MOD y then, n^a = x^a MOD y Yes (r>=1)

34. estudier

(a>=1)

35. sauravshakya

GREAT....... Then I think I proved if n=1,2,3,4,5,6 MOD 7 Then n^6=1 MOD 7

36. estudier

a^(p-1) = 1 mod p (gcd a,p = 1)

37. estudier

p prime

38. NewbieCarrot

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.

39. estudier

a^(p-1) = 1 mod p (p prime, gcd a,p = 1) (OR a^p = a mod p) Fermat's Little Theorem

40. estudier

@sauravshakya

41. estudier

Indirectly related to the "necklace2 problem....

42. sauravshakya

WHAT!

43. sauravshakya

But how???? That is related to permutation and combination.

44. estudier

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

45. estudier

46. estudier

(n^p-n)/2p + [n(p+1/2) -n]/2 + n

47. sauravshakya

Did u mean that every colour has only one bead.

48. estudier

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....