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
Joined
Mar 24, 2019
Messages
7
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.

Screen Shot 2019-03-25 at 10.53.12 am.png
 
Last edited by a moderator:
Thanks! i got the first part, but i'm now stuck in a loop for the second
 
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?
 
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.
 
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.
 
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
 
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.
 
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
 
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).
 
Top