Question

if gcd (a 42)= 1 show that 168=3*7*8 divide a^6-1

Answer 1

since gcd (a, 42) = 1,

gcd(a, 2) = 1
gcd(a, 3) = 1
gcd(a, 7) = 1

Answer 2

hmm...now solve for (a,2)=1 only

Answer 3

sicne 2, 3, 7 are relatively prime
first prove 42 | a^6-1 using fermat's theorem

Answer 4

and then??? how can we convert mod 42 to mod 168???

Answer 5

good question , let me think a bit, i did similar problem few days back. let me see if i can pull it up

Answer 6

ok i m waiting

Answer 7

http://openstudy.com/users/ikram002p#/updates/52a1cb7be4b0a13bbbe8cda1

Answer 8

look at the LAST REPLY of ikram

Answer 9

ok

Answer 10

plz explain this step
2|a^4-1
for a odd (gcd(a,2)=1) (2k+1)^4-1 = (4(...)+1)-1=4(....)
thus 4| a^4-1...............eq2

Answer 11

this is last reply of ikram

Answer 12

since gcd(a, 2) = 1

a = 1 (mod 2)

Answer 13

so,

a^4 = 1 (mod 2)

2 | a^4-1

fine so far ?

Answer 14

yes...next?

Answer 15

then we see that, since gcd(a, 2) = 1, a must be odd.

Answer 16

a = 2k + 1

Answer 17

next, consider : a^4-1

(2k+1)^4 - 1

you can write it as 4(some stuff)

so 4 | a^4-1

Answer 18

that means, gcd(a, 4) = 1

Answer 19

key point is : (2k+1)^4 - 1 is divisible by 4 always

Answer 20

we can say...if any odd no is relatively prime to 2...then it is also relatively prime to every multiple of 2...right?

Answer 21

nope

Answer 22

we can say...if any odd no is relatively prime to 2...then it is also relatively prime to every POWER of 2...

Answer 23

i think u mean that right ?
then it looks right

Answer 24

ok like 9 and 12 are not relatively prime

Answer 25

yeahh

Answer 26

ok...thanks a lot....
now i try to solve...
if i get any confusion i need ur help again...

Answer 27

okay, good luck :)

Answer 28

@ beccaboo022a
in my que a problem arise
(a,2)=1
a=1 mod 2
a^6=1 mod 2
2Ia^6-1
as a is odd so let a=2k+1
but a^6-1=(2k+1)^6-1 is not divisible by 8....:(

Answer 29

I see

Answer 30

to show 8 | a^6-1 :

since 2 | a^6-1
thus, a is odd

say a = 2k + 1

consider : a^2

(2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1
= 8m + 1

Answer 31

thus, a^2 = 1 mod 8

Answer 32

see if that makes some sense.
we used this :- k(k+1) = 2m

Answer 33

ok i understand
a new method:(

Answer 34

thanks

Answer 35

its old method oly :)
just a different way i think

Answer 36

yes:)

Answer 37

so every odd number square is of form 8m + 1