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$
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top