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]

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.

 

[Steven G]

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

Continue from here

 

[GetReal]

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

 

[Dr.Peterson]

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]

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]

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]

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]

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]

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

 

[FriendlyAsian]

don't mind the $

 

[Dr.Peterson]

I figured out another solution:
Because [MATH]d\mid n+1[/MATH] then [MATH]d\mid (n+ 1)(n- 1)=n^2- 1[/MATH] (*)
We also have [MATH]d\mid n^2+ 2 [/MATH] (**)
(**)- (*)=> [MATH]d\mid 3[/MATH]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).

 

[FriendlyAsian]