Modulus theory: If d|n+1 and d|n^2+2, show that d|3; If n=3m, then gcd(n+1,n^2+2)=1.

GetReal

New member
I'm not sure if I've started in the right place.
So far I'm using the assumption that if d divides n+1 then n+1 = d(k). for some integer k
Similarly if d divides n^2+2 then n^2+2=d(m). for some integer m

I've also tried the assumption that, letting a=n+1 and b=n^2+2, then if d divides a and d divides b, then d divides ab. This also reaches a dead end and I'm not sure where to go from there.

Last edited by a moderator:

Jomo

Elite Member
d|(n+1) so n+1 =rd for some integer r
d|(n2+2) so (n2+2) = sd for some integer s
Now n = rd-1
n2+ 2 = (rd-1)2 + 2

Continue from here

GetReal

New member
Thanks! i got the first part, but i'm now stuck in a loop for the second

Dr.Peterson

Elite Member
Use part (a).

What does it tell you about the gcd? What does the fact that n is a multiple of 3 tell you about the gcd?

GetReal

New member
Using part (a).
since n is a multiple of 3 then we can say that 3|n.
then n+1=n(alpha)
and n^2+2 = n(beta)

then we have that the gcd (n^2+2,n+1) = (n^2+2)x + (n+1)y=d
replacing n^2+2 and n+1, we have that
n(alpha)x+n(beta)x=d
n[(alpha)x+(beta)x]=d
Since n=d then n is only divisible by itself and 1.
Therefore GCD=1

Is this correct?
Edit: I also just realised that n+1 for any n that is a multiple of 3 will be the opposite in terms of being even and odd, to n^2+2.

Dr.Peterson

Elite Member
As I think you realize, the first paragraph is wrong; there is no reason to think that n+1 is a multiple of n - in fact, that's only true if n is 1.

Give it another try. Think carefully about my questions, in order.

GetReal

New member
Using (a), since d|3 then we can see that the only divisors of n+1 and n^2+2 are multiples of 3. But because n is a multiple of 3, n+1 and n^2+2 will never be divisible by 3, meaning they are co-prime and the GCD(n+1,n^2+2)=1

Dr.Peterson

Elite Member
Using (a), since d|3 then we can see that the only divisors of n+1 and n^2+2 are multiples of 3. But because n is a multiple of 3, n+1 and n^2+2 will never be divisible by 3, meaning they are co-prime and the GCD(n+1,n^2+2)=1
Not quite. When you conclude that d|3, it doesn't mean that the divisor is a multiple of 3, but that the divisor can only be 1 or 3 (the divisors of 3).

The rest is correct.

FriendlyAsian

New member
I figured out another solution:
Because d$$\displaystyle \mid$$n+1 then d$$\displaystyle \mid$$(n+ 1)(n- 1)=n^2- 1 (*)
We also have d$$\displaystyle \mid$$ n^2+ 2 (**)
(**)- (*)=> d$$\displaystyle \mid$$3
QED

FriendlyAsian

don't mind the $Dr.Peterson Elite Member I figured out another solution: Because $$\displaystyle d\mid n+1$$ then $$\displaystyle d\mid (n+ 1)(n- 1)=n^2- 1$$ (*) We also have $$\displaystyle d\mid n^2+ 2$$ (**) (**)- (*)=> $$\displaystyle d\mid 3$$ QED I've corrected your Latex above; don't use$, and use the [ MATH ] around the entire expression, not individual symbols.

What you have here is a nice proof of part (a). I initially saw yet another way (not as nice).