B 6

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

B 6

G H J

Reveal topic tags

modular arithmetic

relatively prime

Primitive Roots

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.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 2 Y

Y by amar_04, Adventure10

Suppose that $m$ does not have a primitive root. Show that $a^{ \frac{\phi(m)}{2}}\equiv 1 \; \pmod{m}$ for every $a$ relatively prime $m$ .

Z K Y

The post below has been deleted. Click to close.

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

7579 posts

ZetaX

#2 h May 25, 2007, 12:24 AM • 4 Y

Y by Binomial-theorem, esi, Aryan-23, Adventure10

If $m=xy$ with coprime $x,y>2$ , then $2| \varphi(x), \varphi(y)$ , giving:
$a^\frac{\varphi(m)}{2}= a^{\varphi(x) \cdot \frac{\varphi(y)}{2}}\equiv 1^\frac{\varphi(y)}{2}=1 \mod x$
and
$a^\frac{\varphi(m)}{2}= a^{\varphi(y) \cdot \frac{\varphi(x)}{2}}\equiv 1^\frac{\varphi(x)}{2}=1 \mod y.$

After handling the easy case $m=2^{k}\geq 8$ , this now gives our result because for all other $m$ , there are primitive roots.

Z K Y

The post below has been deleted. Click to close.

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

3615 posts

Peter

#3 h Dec 12, 2007, 11:37 PM • 1 Y

Y by Adventure10

ZetaX wrote:

After handling the easy case $m = 2^{k}\geq 8$ , this now gives our result because for all other $m$ , there are primitive roots.

Is this something you can prove here or just a fact that you know?

Z K Y

The post below has been deleted. Click to close.

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

7579 posts

ZetaX

#4 h Dec 13, 2007, 12:09 AM • 2 Y

Y by Adventure10, Mango247

It's near to trivial (and well known):
As there is no primitive root, we have $k \geq 3$ . Trivial checking gives that $a^2 \equiv 1 \mod 8$ and inductively we have $a^{2^{r-2}} \equiv 1 \mod 2^r$ implying (by $a^{2^{r-2}} =1+2^r b$ ) that $a^{2^{r-1}} = (1+2^r b)^2 = 1+ 2^{r+1} b + 2^{2r} b \equiv 1 \mod 2^{r+1}$ .

This post has been edited 1 time. Last edited by ZetaX, Apr 27, 2014, 8:56 AM

Z K Y

The post below has been deleted. Click to close.

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

3280 posts

#5 h Jan 18, 2014, 9:00 PM • 1 Y

Y by Adventure10

how do u have a=1+(2^r)b? for r = 3, that means a is 1 or 9 mod 16 (if we prove the r+1 case), but that missed the other residues in 16

Z K Y

The post below has been deleted. Click to close.

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

7579 posts

ZetaX

#6 h Apr 27, 2014, 8:55 AM • 2 Y

Y by Adventure10, Mango247

There is simply a missing exponent.

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#7 h May 8, 2020, 5:22 PM

Y by

we prove for any prime factor of $n$ that $||m||_p=k$ that $a^{ \frac{\varphi(m)}{2}}\equiv 1 \; \pmod{p^k}$

first of all it's easy to see that $\varphi(\frac{m}{p^k})$ is even because $\frac{m}{p^k} >2$

now let $x=\frac{\varphi(m)}{2} =\frac{\varphi(\frac{m}{p^k}) \times (p-1)p^{k-1}}{2} =\frac{\varphi(\frac{m}{p^k})}{2} \times (p-1)p^{k-1} \implies \varphi(p^k) \mid x \implies a^x \equiv 1 \mod p^k$

because $p$ was an arbitrary prime factor then $a^x \equiv 1 \mod m$

This post has been edited 5 times. Last edited by H.HAFEZI2000, May 8, 2020, 5:26 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a