A Tricky Divisibility Problem

[sudeepsingh]

Shouldn't it be d divides gcd(p-1, 2n)? Of course, d will still end up having the same possible values 1/2.

[mathcanbeeasy]

gcd(p-1, 2n)=1 or 2, can be explained more clearly and more completely, for students, as follows: If p is 2, it is clear that gcd is 1. If p is the smallest prime different from 2, then it is odd. So 2 is no longer a factor of n because otherwise 2 would be the smallest factor. Thus in the expression 2*n, 2 appears only once as a prime factor because n no longer has a prime factor of 2. At the same time p-1 is even and is smaller than p. So it has a factor of 2 and any other prime factor of p-1 is less than p. So gcd will be 2*a possible prime number smaller than p. But that would mean that that prime factor smaller than p would be a prime factor of n, which is not possible because p is the smallest. So the only common prime factor will be 2. In fact, there was no need for gcd either, the fact that 2 is the only factor was enough. Obviously, being the only one, it is also the biggest.

[eduardciuca]

After I watched this I was thinking at the (possible) unsolvable problem:
Let a, b, n > 1 and k an integer .
Find all n such that n^a divides b^n + k
Now, the problem stated in this video corresponds to a=2, b=3 and k=1.

[mrityunjaykumar]

their is a simply easy trick for the question.. => d=order of 3(mod p)| 2n also..since 3^n≡-1(mod p) =>d∤n=>d|2=> d=2 or 1..

[johnvandenberg]

2|n (6:57) why? All I know is that 2|2n. Probably one has to reason as follows: 3^n + 1 is even (induction or binomial expansion of (2+1)^n)), so n^2 is even, therefore n is even.

[iainfulton]

It will only work for n =1 otherwise you'll have 2 numbers 2 apart being able to divide a power of 3.

[mcwulf]

I got the same answer a simpler way. Although I think this has holes in it.
If kn^2 = 3^n + 1
Then if 3 and n are coprime we can use FLT and we have
0 == 3+1 (mod n)
So n must be 4 or a factor of 4.
So just try 1, 2 and 4.

Of course this wouldn't work if GCD(3, n) = 3.

[bait]

Seems strange to be able to reference FLT and not congruent/modulo cycle/period/order

[fblyzwf]

How to prove that gcd (p-1, 2n)=d with euclidean algorithm, i don't seem to understand.

[drynshock]

If p | 3^n -1, we know that 3^n-1 is an even number, since p is the smalles prime that divides n then p=2.

[ЯЕРКАНАТ]

If n=2k+1>1 then 3^n+1/n is not integer

[vitorvg]

n|3^n-1 does anyone know how to solve this?? I know if n>1, then 2 must divide n. I think n=2^k, k=0, 1, 2, ... is the answer, but can't prove it.

[hokyung]

why gcd(p-1, 2n)=1or2 ? I don't understand clear. Maybe n is divided by p so if p is 3, gcd(p-1, 2n)=2 /if p is not 3, gcd(p-1, 2n)=1 ?

[tiktokclips]

Why did he use p|3²-1
That means he took n=1 but he shouldn't do this because n has prime factors
I think you didn't find a contradiction but you made it yourself

[adamherzenberg]

I feel like this is pretty easy, n^2 is always divisible into n^3 so for it to be divisible into n^3+1 n has to be equal to 1 cause nothing else would make sense.

[TechyMage]

N=1, 2 i don't care about other values