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:

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,276
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
Joined
Mar 24, 2019
Messages
7
Thanks! i got the first part, but i'm now stuck in a loop for the second
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,319
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
Joined
Mar 24, 2019
Messages
7
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
Joined
Nov 12, 2017
Messages
3,319
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
Joined
Mar 24, 2019
Messages
7
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
Joined
Nov 12, 2017
Messages
3,319
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
Joined
Mar 22, 2019
Messages
9
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

New member
Joined
Mar 22, 2019
Messages
9
don't mind the $
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,319
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).
 

FriendlyAsian

New member
Joined
Mar 22, 2019
Messages
9
11560
 
Top