Prove or disprove...

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Prove or disprove...

G H J

Reveal topic tags

modular arithmetic

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

308 posts

#1 h Nov 16, 2006, 11:49 AM • 2 Y

Y by Adventure10, Mango247

The following statement is true or false?

If $GCD(2^{n}+1,n!-1) > 1$ then $GCD(2^{n}+1,n!-1) = 2n+1$ .

It is verified for $n$ up to $45,000$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

667 posts

#2 h Nov 17, 2006, 11:14 AM • 2 Y

Y by Adventure10, Mango247

Can you prove that there are infinite many $n$ such that $GCD(2^{n}+1,n!-1)>1$ ?I think this one should be consider first,though I have no idea about both these two problems....

It is too hard for me

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

629 posts

maxal

#3 h Nov 17, 2006, 11:30 PM • 2 Y

Y by Adventure10, Mango247

If $p=2n+1$ is prime then Wilson's theorem implies
$(n!)^{2}\equiv (-1)^{n}(2n)! \equiv (-1)^{n+1}\pmod{p}.$
Then for $n=4k+1$ we have $n! = \pm 1\pmod{p}$ and $2^{n}\equiv-1\pmod{p}.$
If $n! = 1\pmod{p}$ then $p$ divides $\gcd(2^{n}+1,n!-1).$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#4 h Oct 27, 2007, 5:02 PM • 2 Y

Y by Adventure10, Mango247

Call prime p special if
$p|gcd(2^{(p - 1)/2} + 1,n! - 1)$
and exclusive if exist $n\not \frac {p - 1}{2}$ , suth that $p|gcd(2^n + 1,n! - 1).$
It is easy to prove, that $p$ is special if and only if $p = 3\mod 8$ and $\frac {h + 1}{2}$ is even, were $h$ is number of classes $Q(\sqrt{-p})$ (or number of quadratic residius less than $p/2$ - odd, or there are odd number of odd quadratic residius).
There are 3 exclusive primes, less than 5 000 000:
$p = 521881, \ n = 221799, \ n = 300081,$
$p = 774593, \ n = 338884,$
$p = 4327489, \ n = 3652374.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#5 h Oct 28, 2007, 2:23 PM • 2 Y

Y by Adventure10, Mango247

heartwork wrote:

The following statement is true or false?

If $GCD(2^{n} + 1,n! - 1) > 1$ then $GCD(2^{n} + 1,n! - 1) = 2n + 1$ .

It is verified for $n$ up to $45,000$ .

Sorry I don't read above solution . Here is mysolution :
The $n\in N$ satisfy the condition then $2n + 1$ is a prime in the form $8k + 3,8k + 5$
Proof $2n + 1|n! - 1$
If $2n + 1$ is a composite then it can represent in the form $ab$ where $a,b\geq 2$
Imply that $\min\{a,b\} < n$ so $\min\{a,b\}\not |n! - 1$
So $2n + 1 = p$
$p|2^{\frac {p - 1}{2}} + 1 \Longleftrightarrow p\equiv 3,5 (\mod 8)$
So the statement true for n in this form.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#6 h Oct 28, 2007, 2:49 PM • 2 Y

Y by Adventure10, Mango247

TTsphn wrote:

So $2n + 1 = p$
$p|2^{\frac {p - 1}{2}} + 1 \Longleftrightarrow p\equiv 3,5 (\mod 8)$
So the statement true for n in this form.

The statment equavalent, that there are not exclusive pairs (p,n). I found exclusive pairs, therefore statment is not true.
If $p=1\mod 4$ , then $(\frac{p-1}{2}!)^2=-1\mod p$ , therefore $p\not |\frac{p-1}{2}!-1$ or p is not special.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#7 h Oct 28, 2007, 2:58 PM • 1 Y

Y by Adventure10

Oh I am sorry have a mistake .
$p|(\frac{p-1}{2})!-1$
Imply that $p\equiv 3 (\mod 4)$ so it has form $8k+3$
But it is only necessary.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#8 h Oct 28, 2007, 3:22 PM • 1 Y

Y by Adventure10

Rust wrote:

Call prime p special if
$p|gcd(2^{(p - 1)/2} + 1,n! - 1)$
and exclusive if exist $n\not \frac {p - 1}{2}$ , suth that $p|gcd(2^n + 1,n! - 1).$
It is easy to prove, that $p$ is special if and only if $p = 3\mod 8$ and $\frac {h + 1}{2}$ is even, were $h$ is number of classes $Q(\sqrt { - p})$ (or number of quadratic residius less than $p/2$ - odd, or there are odd number of odd quadratic residius).
There are 3 exclusive primes, less than 5 000 000:
$p = 521881, \ n = 221799, \ n = 300081,$
$p = 774593, \ n = 338884,$
$p = 4327489, \ n = 3652374.$

Your condition $\Longleftrightarrow p|(\frac{p-1}{2})!-1$ and it is not clear for n large enoght.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#9 h Oct 28, 2007, 3:22 PM • 1 Y

Y by Adventure10

If $p=3\mod 8$ , then $p|2^{(p-1)/2}+1$ and $n=(p-1)/2, \ n!=\pm 1\mod p$ (because for $n=(p-1)/2$ we get $-1\equiv (2n)!\equiv (p-1)...(p-n)n!\equiv (-1)^nn!n!$ , it give $n!=\pm 1\mod p$ ).
If we have odd number quadratic residius in set $\{1,2,...,n\}$ mod p, then $n!$ is quadratic residius mod p. But for $p=3\mod 8$ -1 is not quadratic residius. Therefore in these case must be $n!=1\mod p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#10 h Oct 28, 2007, 3:24 PM • 2 Y

Y by Adventure10, Mango247

Rust wrote:

If $p = 3\mod 8$ , then $p|2^{(p - 1)/2} + 1$ and $n = (p - 1)/2, \ n! = \pm 1\mod p$ (because for $n = (p - 1)/2$ we get $- 1\equiv (2n)!\equiv (p - 1)...(p - n)n!\equiv ( - 1)^nn!n!$ , it give $n! = \pm 1\mod p$ ).
If we have odd number quadratic residius in set $\{1,2,...,n\}$ mod p, then $n!$ is quadratic residius mod p. But for $p = 3\mod 8$ -1 is not quadratic residius. Therefore in these case must be $n! = 1\mod p$ .

Yes it is quadric reside with Gauss Lemma .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a