Question

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

Answer 1

i assume we cannot consider 0

Answer 2

Humph...

Answer 3

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

Answer 4

@estudier i think all numbers can be expressed that way

Answer 5

(7k + r)^3 = (7k + r)^2

would that help - i'm clutching at straws to be honest!!

Answer 6

So I think it is 7k+1

Answer 7

?

Answer 8

"(7k + r)^3 = (7k + r)^2"

Maybe expand these instead of setting them equal...

Answer 9

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

Answer 10

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

Answer 11

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

Yes, I said that above....

Answer 12

oh.....THAT WAS A HINT

Answer 13

The question does say 7k or 7k +1

Answer 14

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.

Answer 15

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

Answer 16

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.

Answer 17

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

Answer 18

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

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

Answer 19

@estudier You got it.

Answer 20

Not done yet....

Answer 21

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)

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

r = [1,6]

Answer 26

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

True, but a little more explanation would be nice...:-)

Answer 27

0 also

Answer 28

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

Answer 29

Yes, that's right, well done.

Answer 30

Just include r= 0 as well....

Answer 31

oh yes... .

Answer 32

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

Answer 33

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

Yes (r>=1)

Answer 34

(a>=1)

Answer 35

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

Answer 36

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

Answer 37

p prime

Answer 38

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.

Answer 39

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

Fermat's Little Theorem

Answer 40

@sauravshakya

Answer 41

Indirectly related to the "necklace2 problem....

Answer 42

WHAT!

Answer 43

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

Answer 44

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

Answer 45

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?

Answer 46

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

Answer 47

Did u mean that every colour has only one bead.

Answer 48

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