Mixing
If $minx inmathbbN : xn+1 text is a square geq fracn4$ then n is prime.
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Let $n$ be a odd natural number greater than 3 and $k=minx inmathbbN : xn+1 text is a square$ and $t=minx inmathbbN : xn text is a square.$ If $k>fracn4$ and $t>fracn4$ then n is prime.
I proved second direction easily, so I don't cite it. If $n$ is composite and isn't squarefree the hypothese about $t$ is false and it's very easy from prime decomposition. I have problems wiith a part about composite squarefree $n$. I tried prime decomposition, I tried find explicitly k to contradict. I spent a few hours. I would be very grateful for any hint.
number-theory elementary-number-theory prime-numbers
asked Jul 22 at 15:09
jpatrick
379212
add a comment |Â
up vote
3
down vote
favorite
Let $n$ be a odd natural number greater than 3 and $k=minx inmathbbN : xn+1 text is a square$ and $t=minx inmathbbN : xn text is a square.$ If $k>fracn4$ and $t>fracn4$ then n is prime.
I proved second direction easily, so I don't cite it. If $n$ is composite and isn't squarefree the hypothese about $t$ is false and it's very easy from prime decomposition. I have problems wiith a part about composite squarefree $n$. I tried prime decomposition, I tried find explicitly k to contradict. I spent a few hours. I would be very grateful for any hint.
number-theory elementary-number-theory prime-numbers
asked Jul 22 at 15:09
jpatrick
379212
2
Take $n=6$. Then $k=4$ and $t=6$. Since $4$ and $6$ are bigger than $n/4=6/4$, it follows that $6$ is prime. Contradiction.
– Dietrich Burde
Jul 22 at 15:15
Can you clarify your question? The first composite square free number is already a counterexample, yes? So's the second..$n=10implies k=8,t=10$. Which composite square free numbers did you try?
– lulu
Jul 22 at 15:20
Is $n$ maybe supposed to be odd?
– Daniel Fischer♦
Jul 22 at 15:21
Clearly, I forget about hypotheses...
– jpatrick
Jul 22 at 15:31
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $n$ be a odd natural number greater than 3 and $k=minx inmathbbN : xn+1 text is a square$ and $t=minx inmathbbN : xn text is a square.$ If $k>fracn4$ and $t>fracn4$ then n is prime.
I proved second direction easily, so I don't cite it. If $n$ is composite and isn't squarefree the hypothese about $t$ is false and it's very easy from prime decomposition. I have problems wiith a part about composite squarefree $n$. I tried prime decomposition, I tried find explicitly k to contradict. I spent a few hours. I would be very grateful for any hint.
number-theory elementary-number-theory prime-numbers
asked Jul 22 at 15:09
jpatrick
379212
Let $n$ be a odd natural number greater than 3 and $k=minx inmathbbN : xn+1 text is a square$ and $t=minx inmathbbN : xn text is a square.$ If $k>fracn4$ and $t>fracn4$ then n is prime.
I proved second direction easily, so I don't cite it. If $n$ is composite and isn't squarefree the hypothese about $t$ is false and it's very easy from prime decomposition. I have problems wiith a part about composite squarefree $n$. I tried prime decomposition, I tried find explicitly k to contradict. I spent a few hours. I would be very grateful for any hint.
number-theory elementary-number-theory prime-numbers
asked Jul 22 at 15:09
jpatrick
379212
edited Jul 22 at 15:31
asked Jul 22 at 15:09
jpatrick
379212
asked Jul 22 at 15:09
jpatrick
379212
asked Jul 22 at 15:09
jpatrick
379212
379212
2
Take $n=6$. Then $k=4$ and $t=6$. Since $4$ and $6$ are bigger than $n/4=6/4$, it follows that $6$ is prime. Contradiction.
– Dietrich Burde
Jul 22 at 15:15
Can you clarify your question? The first composite square free number is already a counterexample, yes? So's the second..$n=10implies k=8,t=10$. Which composite square free numbers did you try?
– lulu
Jul 22 at 15:20
Is $n$ maybe supposed to be odd?
– Daniel Fischer♦
Jul 22 at 15:21
Clearly, I forget about hypotheses...
– jpatrick
Jul 22 at 15:31
add a comment |Â
2
Take $n=6$. Then $k=4$ and $t=6$. Since $4$ and $6$ are bigger than $n/4=6/4$, it follows that $6$ is prime. Contradiction.
– Dietrich Burde
Jul 22 at 15:15
Can you clarify your question? The first composite square free number is already a counterexample, yes? So's the second..$n=10implies k=8,t=10$. Which composite square free numbers did you try?
– lulu
Jul 22 at 15:20
Is $n$ maybe supposed to be odd?
– Daniel Fischer♦
Jul 22 at 15:21
Clearly, I forget about hypotheses...
– jpatrick
Jul 22 at 15:31
2
2
Take $n=6$. Then $k=4$ and $t=6$. Since $4$ and $6$ are bigger than $n/4=6/4$, it follows that $6$ is prime. Contradiction.
– Dietrich Burde
Jul 22 at 15:15
Take $n=6$. Then $k=4$ and $t=6$. Since $4$ and $6$ are bigger than $n/4=6/4$, it follows that $6$ is prime. Contradiction.
– Dietrich Burde
Jul 22 at 15:15
Can you clarify your question? The first composite square free number is already a counterexample, yes? So's the second..$n=10implies k=8,t=10$. Which composite square free numbers did you try?
– lulu
Jul 22 at 15:20
Can you clarify your question? The first composite square free number is already a counterexample, yes? So's the second..$n=10implies k=8,t=10$. Which composite square free numbers did you try?
– lulu
Jul 22 at 15:20
Is $n$ maybe supposed to be odd?
– Daniel Fischer♦
Jul 22 at 15:21
Is $n$ maybe supposed to be odd?
– Daniel Fischer♦
Jul 22 at 15:21
Clearly, I forget about hypotheses...
– jpatrick
Jul 22 at 15:31
Clearly, I forget about hypotheses...
– jpatrick
Jul 22 at 15:31
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
If $nin mathbbN$ is odd and not a prime power, then there is always an $a$ such that $1 < a leqslant fracn-12$ and $a^2 equiv 1 pmodn$. Then it follows that
$$k leqslant fraca^2-1n < fracn^2/4n = fracn4,.$$
To see that such an $a$ exists, let $p$ be a prime dividing $n$, and write $n = p^rcdot m$ with $p nmid m$. Since $n$ is not a prime power, we have $m > 1$. By the Chinese remainder theorem, there is a $0 < b < n$ such that $b equiv 1 pmodp^r$ and $b equiv -1 pmodm$. Since $b equiv 1 pmodp^r$ we have $b neq n-1$, and since $b equiv -1 pmodm$ we have $b neq 1$, thus $1 < b < n-1$. If $b leqslant fracn-12$, put $a = b$, else put $a = n-b$. Then $1 < a leqslant fracn-12$, and $a^2 equiv (pm 1)^2 equiv 1 pmodp^r$ and $a^2 equiv (mp 1)^2 equiv 1 pmodm$, so we indeed have $a^2 equiv 1 pmodn$.
If $n$ is an odd prime power and not a prime, then $n = p^r$ for some odd prime $p$ and $r > 1$. If $r$ is even, then $n$ is already a square and so $t = 1 < fracn4$. If $r$ is odd, then $pn$ is the smallest square multiple of $n$, and $t = p leqslant fracnp^2 leqslant fracn9 < fracn4$.
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
If $nin mathbbN$ is odd and not a prime power, then there is always an $a$ such that $1 < a leqslant fracn-12$ and $a^2 equiv 1 pmodn$. Then it follows that
$$k leqslant fraca^2-1n < fracn^2/4n = fracn4,.$$
To see that such an $a$ exists, let $p$ be a prime dividing $n$, and write $n = p^rcdot m$ with $p nmid m$. Since $n$ is not a prime power, we have $m > 1$. By the Chinese remainder theorem, there is a $0 < b < n$ such that $b equiv 1 pmodp^r$ and $b equiv -1 pmodm$. Since $b equiv 1 pmodp^r$ we have $b neq n-1$, and since $b equiv -1 pmodm$ we have $b neq 1$, thus $1 < b < n-1$. If $b leqslant fracn-12$, put $a = b$, else put $a = n-b$. Then $1 < a leqslant fracn-12$, and $a^2 equiv (pm 1)^2 equiv 1 pmodp^r$ and $a^2 equiv (mp 1)^2 equiv 1 pmodm$, so we indeed have $a^2 equiv 1 pmodn$.
If $n$ is an odd prime power and not a prime, then $n = p^r$ for some odd prime $p$ and $r > 1$. If $r$ is even, then $n$ is already a square and so $t = 1 < fracn4$. If $r$ is odd, then $pn$ is the smallest square multiple of $n$, and $t = p leqslant fracnp^2 leqslant fracn9 < fracn4$.
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
add a comment |Â
up vote
4
down vote
accepted
If $nin mathbbN$ is odd and not a prime power, then there is always an $a$ such that $1 < a leqslant fracn-12$ and $a^2 equiv 1 pmodn$. Then it follows that
$$k leqslant fraca^2-1n < fracn^2/4n = fracn4,.$$
To see that such an $a$ exists, let $p$ be a prime dividing $n$, and write $n = p^rcdot m$ with $p nmid m$. Since $n$ is not a prime power, we have $m > 1$. By the Chinese remainder theorem, there is a $0 < b < n$ such that $b equiv 1 pmodp^r$ and $b equiv -1 pmodm$. Since $b equiv 1 pmodp^r$ we have $b neq n-1$, and since $b equiv -1 pmodm$ we have $b neq 1$, thus $1 < b < n-1$. If $b leqslant fracn-12$, put $a = b$, else put $a = n-b$. Then $1 < a leqslant fracn-12$, and $a^2 equiv (pm 1)^2 equiv 1 pmodp^r$ and $a^2 equiv (mp 1)^2 equiv 1 pmodm$, so we indeed have $a^2 equiv 1 pmodn$.
If $n$ is an odd prime power and not a prime, then $n = p^r$ for some odd prime $p$ and $r > 1$. If $r$ is even, then $n$ is already a square and so $t = 1 < fracn4$. If $r$ is odd, then $pn$ is the smallest square multiple of $n$, and $t = p leqslant fracnp^2 leqslant fracn9 < fracn4$.
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
If $nin mathbbN$ is odd and not a prime power, then there is always an $a$ such that $1 < a leqslant fracn-12$ and $a^2 equiv 1 pmodn$. Then it follows that
$$k leqslant fraca^2-1n < fracn^2/4n = fracn4,.$$
To see that such an $a$ exists, let $p$ be a prime dividing $n$, and write $n = p^rcdot m$ with $p nmid m$. Since $n$ is not a prime power, we have $m > 1$. By the Chinese remainder theorem, there is a $0 < b < n$ such that $b equiv 1 pmodp^r$ and $b equiv -1 pmodm$. Since $b equiv 1 pmodp^r$ we have $b neq n-1$, and since $b equiv -1 pmodm$ we have $b neq 1$, thus $1 < b < n-1$. If $b leqslant fracn-12$, put $a = b$, else put $a = n-b$. Then $1 < a leqslant fracn-12$, and $a^2 equiv (pm 1)^2 equiv 1 pmodp^r$ and $a^2 equiv (mp 1)^2 equiv 1 pmodm$, so we indeed have $a^2 equiv 1 pmodn$.
If $n$ is an odd prime power and not a prime, then $n = p^r$ for some odd prime $p$ and $r > 1$. If $r$ is even, then $n$ is already a square and so $t = 1 < fracn4$. If $r$ is odd, then $pn$ is the smallest square multiple of $n$, and $t = p leqslant fracnp^2 leqslant fracn9 < fracn4$.
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
If $nin mathbbN$ is odd and not a prime power, then there is always an $a$ such that $1 < a leqslant fracn-12$ and $a^2 equiv 1 pmodn$. Then it follows that
$$k leqslant fraca^2-1n < fracn^2/4n = fracn4,.$$
To see that such an $a$ exists, let $p$ be a prime dividing $n$, and write $n = p^rcdot m$ with $p nmid m$. Since $n$ is not a prime power, we have $m > 1$. By the Chinese remainder theorem, there is a $0 < b < n$ such that $b equiv 1 pmodp^r$ and $b equiv -1 pmodm$. Since $b equiv 1 pmodp^r$ we have $b neq n-1$, and since $b equiv -1 pmodm$ we have $b neq 1$, thus $1 < b < n-1$. If $b leqslant fracn-12$, put $a = b$, else put $a = n-b$. Then $1 < a leqslant fracn-12$, and $a^2 equiv (pm 1)^2 equiv 1 pmodp^r$ and $a^2 equiv (mp 1)^2 equiv 1 pmodm$, so we indeed have $a^2 equiv 1 pmodn$.
If $n$ is an odd prime power and not a prime, then $n = p^r$ for some odd prime $p$ and $r > 1$. If $r$ is even, then $n$ is already a square and so $t = 1 < fracn4$. If $r$ is odd, then $pn$ is the smallest square multiple of $n$, and $t = p leqslant fracnp^2 leqslant fracn9 < fracn4$.
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
answered Jul 22 at 18:44
Daniel Fischer♦
171k16154274
171k16154274
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
add a comment |Â
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
A minor point (not a mistake). If $n>1$ is odd, composite, and not a prime power then $bequiv -1 mod mimplies bne 1$ because $mnot in 1,2.$
– DanielWainfleet
Jul 23 at 5:51
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859487%2fif-min-x-in-mathbbn-xn1-text-is-a-square-geq-fracn4-then-n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Take $n=6$. Then $k=4$ and $t=6$. Since $4$ and $6$ are bigger than $n/4=6/4$, it follows that $6$ is prime. Contradiction.
– Dietrich Burde
Jul 22 at 15:15
Can you clarify your question? The first composite square free number is already a counterexample, yes? So's the second..$n=10implies k=8,t=10$. Which composite square free numbers did you try?
– lulu
Jul 22 at 15:20
Is $n$ maybe supposed to be odd?
– Daniel Fischer♦
Jul 22 at 15:21
Clearly, I forget about hypotheses...
– jpatrick
Jul 22 at 15:31