MHB P-1 consecutive numbers coprime to n

  • Thread starter Thread starter shmounal
  • Start date Start date
  • Tags Tags
    Numbers
AI Thread Summary
For an integer n greater than 1, its smallest prime factor p limits the number of consecutive positive integers coprime to n to at most p - 1. If there were more than p - 1 consecutive integers, they would share a prime factor with n, violating coprimality. The maximum of p - 1 can be achieved by demonstrating p - 1 consecutive integers that are coprime to n. The greatest common divisor of p - 1 and n is p - 1 itself. Additionally, it can be shown that 2^n does not equal 1 modulo n.
shmounal
Messages
3
Reaction score
0
a) Let an integer $n > 1$ be given, and let $p$ be its smallest prime factor. Show
that there can be at most $p − 1$ consecutive positive integers coprime to $n$.
b) Show further that the number $p − 1$ in (a) cannot be decreased, by exhibiting
$p − 1$ consecutive positive integers coprime $n$.
c) What is gcd$(p − 1, n)$?
d)Show that $2^n \not\equiv 1 (mod n)$.

I think the first part has something to with the fact that two positive integers are coprime iff they have no prime factors in common. As if there were more than $p-1$ consecutive numbers then they would have a coprime in common. Not sure how to word this convincingly!

Not sure for b). Guessing I'd say c) is $p-1$, though not sure. d).. no clue!

If you can point me in the right direction I'd appreciate it, thanks.
 
Mathematics news on Phys.org
shmounal said:
a) Let an integer $n > 1$ be given, and let $p$ be its smallest prime factor. Show
that there can be at most $p − 1$ consecutive positive integers coprime to $n$.
b) Show further that the number $p − 1$ in (a) cannot be decreased, by exhibiting
$p − 1$ consecutive positive integers coprime $n$.
c) What is gcd$(p − 1, n)$?
d)Show that $2^n \not\equiv 1 (mod n)$.

I think the first part has something to with the fact that two positive integers are coprime iff they have no prime factors in common. As if there were more than $p-1$ consecutive numbers then they would have a coprime in common. Not sure how to word this convincingly!

Not sure for b). Guessing I'd say c) is $p-1$, though not sure. d).. no clue!

If you can point me in the right direction I'd appreciate it, thanks.

Considering that the number of coprimes of n is the Euler's function...

$\displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

... if $p_{0}$ is the smallest prime dividing n then is...

$\displaystyle \varphi(n)= \frac{n}{p_{0}}\ (p_{0}-1)\ \prod_{p|\frac{n}{p_{0}}} (1-\frac{1}{p})$ (2)

... and in any case the term $p_{0}-1$ is a factor of $\varphi(n)$...

Kind regards

$\chi$ $\sigma$
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Just chatting with my son about Maths and he casually mentioned that 0 would be the midpoint of the number line from -inf to +inf. I wondered whether it wouldn’t be more accurate to say there is no single midpoint. Couldn’t you make an argument that any real number is exactly halfway between -inf and +inf?
Back
Top