Linked Questions

17
votes
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 ...
11
votes
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 ...
6
votes
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 ...
0
votes
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^...
1
vote
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$,...
3
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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?
1
vote
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)$
0
votes
3answers
77 views

If $2^x \equiv 2^4 + 2^4 \pmod 7$, then what is the value of $\mathbf x$?

It's easy to figure out the answer which is 2. But I am trying to solve it in a different approach. My approach: $2^x \equiv 2^4 + 2^4 \pmod 7 \Rightarrow x\log_2(2) \equiv 4\log_2(2) + 4\log_2(2) \...
1
vote
2answers
49 views

Question about Lagrange's and factor theorem

Find all solutions $x^{12} \equiv 1 \pmod{13}$. Hint: the computation of high powers is better accomplished by using binary expansion of the exponent. Approach: This time I don't have a clear ...
1
vote
1answer
45 views

additive order of any zero divisor in $Z_{p^2}$ is p, is it true?

This result was used in a proof of a theorem, i am not sure if it's true. can someone tell the proof idea. Can it be generalized to additive order of any zero divisor in $Z_{p^k}$, is there any ...