# Linked Questions

2answers
5k views

### Order of an Element Modulo $n$ Divides $\phi(n)$

How can I show that the order of an element modulo $n$ divides $\phi(n)$? I know that if $a$ and $n$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod n$ is its ...
3answers
3k views

### A theorem about prime divisors of generalized Fermat numbers?

A theorem of Édouard Lucas related to the Fermat numbers states that : Any prime divisor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k\cdot 2^{n+2}+1$ whenever $n$ is greater than one. Does anyone ...
4answers
233 views

### How to prove that no prime factor of $x^2-x+1$ is of the form $6k-1$

Consider sequence $x^2-x+1$ ($1,3,7,13,21,31,43,57,73,91,\dots$). Let's consider prime factorization of each term. $$3=3$$ $$7=7$$ $$13=13$$ $$21=3\times7$$ It seems that the only prime factors we ...
2answers
110 views

### Let $a=2^{2^{35}} +1,b=2^{2^{21}} +1$ , then the greatest common divisor of $a$ and $b$ is…?

Let $a=2^{2^{35}} +1, b=2^{2^{21}} +1$. Then $\gcd(a,b)$ is My little work : $$a -2 =(2^{2^{22}})^K -1$$ where $K=2^{14}$. $(2^{2^{22}})^K -1$ is divisible by$(2^{2^{22}}) -1$ \implies a-2= (2^...
1answer
123 views

### Divisor of $2^{2^n} + 1$ modulus $2^{n+1}$

I'm stuck at the following question: let $d$ divide $2^{2^n} +1$. Show that $d \equiv 1 \pmod{2^{n+1}}$. All I've managed to do so far was to notice that $2^{n+1} \mid 2^{2^n}$ for every natural $n$,...
2answers
81 views

### Divisible rule for $73$ - how to prove?

How we can prove divisible rules for larger primes like $73$? $n$ is dividable by $73$ if and only if $73|a-b$ where $a$ is number from first $4$ digits $b$ is number from rest of digits ...
2answers
78 views

### Prove $g$ is a generator if $g^q=1 \pmod p$

Let $p$ be an odd prime and let $q=\frac{p-1}{2}$. If $g^q=-1\pmod p$ and $q$ is a prime, show that $g$ is a primitive root mod $p$. I want to show $\{g,g^1,...,g^{p-1}\}=\{1,2,...p-1\}$. I argue by ...
2answers
67 views

### Computing the order of $[9]_{31}$ in $(\mathbb{Z}/31\mathbb{Z})^*$

A part of Aluffi's "Algebra: Chapter 0" exercise II.4.12 suggests computing the order of $[9]_{31}$ in $(\mathbb{Z}/31\mathbb{Z})^*$. Sure, I could just multiply $9$ a few times until I get $1$ as a ...
1answer
67 views

### Minimal integer to make a rational into an integer

Let $q = \frac ab$ be any rational number such that $a < b$. What is the smallest positive integer $n$ such that $\frac ab \times \left(2^n-1\right)$ is an integer?
3answers
69 views

### A problem on congruent equation

Can someone help me to solve the following congruent equation. I have tried to use Fermat's little theorem but failed to solve this: $x^{12}=87(\mod 101)$
3answers
77 views