# Tagged Questions

Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

44 views

### Prove that $\varphi(m)+ \tau(m)\leqslant m+1$

Prove that $\varphi(m)+ \tau(m)\leqslant m+1$ where $m\in \mathbb N$ I wrote $m:=p_1^{\alpha_ 1}....p_s^{\alpha _s}$ $$\varphi(m)=p_1^{\alpha_1}(p_1-1)...p_s^{\alpha_s}(p_s-1)$$ ...
17 views

### If n has at least one primitive element, what is the total number of primitive elements modulo n? [duplicate]

If n has at least one primitive element, what is the total number of primitive elements modulo n? Do I need to do any calculation on this or what Am I supposed to know to solve this?
21 views

### Use Hensel's lemma to show that if $a^n\equiv 1\mod{p}$ then $\exists b$ $b^n\equiv 1\mod{p^r}$

Let $p$ be an odd prime, and let $n$ be a natural number such that $n\mid p-1$. Suppose $1\neq a\in\mathbb{Z}$ is such that $a^n\equiv 1\mod{p}$, and use Hensel's lemma to show that for any given ...
18 views

### Congruent powers implies numbers are congruent

Let $N\in\mathbb{N}$, and let $m,n$ be coprime. Also, suppose $a,b$ are relatively prime to $N$, and that $$a^n\equiv b^n\mod{N},\ a^m\equiv b^m\mod{N}$$ I need to show that $a\equiv b\mod{N}$. I ...
69 views

### Is the numbers of primes that is sum of 2 + another prime is finite?

In order to have sum of $2$-primes to be a prime one of the primes must be the prime $2$. However the "distance" between adjacent primes increases as we search along the natural numbers. For example ...
36 views

### Proving a is a quadratic residue using that there is some x∈Z so that ordp(x)=p−1

Let $p>2$ be an odd prime, and assume there is some $x\in \mathbb{Z}$ so that ${\rm ord }_p (x)=p−1$. Use this assumption to prove that: a) If $p$ is an odd prime, $p$ does not divide $a$, and $a$ ...
12 views

### The number of pairs of coprimes in a given range

Let $n_{11} \le a \le n_{12}$ and $n_{21} \le b \le n_{22}$ be integers. Is there a formula $f$ which gives the number of the pairs $\left<a,b\right>$ which are relatively prime, that is, ...
39 views

### Solutions to the diophantine equation $6x^2 - 6x - y^2 + y=0$?

Are there any positive integer solutions to the diophantine equation in the title other than $(1,1)$? This equation looks easy enough so it could be that there is some simple argument that shows ...
35 views

### Congruence Modulo involving factorials

How do I show that $23!\equiv 21! \pmod{101}$? I tried using a calculator but the numbers are so big that am finding it hard to prove. How can factorials be broken down so that they can be easily ...
31 views

### Proving a congrent modular

How do I show that $3^{1974}+5^{1974}\equiv 0 \pmod {13}$? I have tried feeding the values onto a calculator but they are so big to be computed. What is the best approach?
72 views

### Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
38 views

### Smallest positive integer n

The smallest positive integer $n$ with $24$ divisors (where $1$ and $n$ are also considered as divisors of $n$) is? As far as I know it can be solved like this: prime factors of $24$ are : ...
45 views

### A conditional inequality which itself implies a sharper version of it [duplicate]

Problem: Given that $m, n$ are positive integers such that $\sqrt{7} -\frac{m}{n} > 0$. Then show that $\sqrt{7}-\frac{m}{n} > \frac{1}{mn}$. I have failed to do this fascinating problem. My ...
43 views

### How to improve this proof?

I was doing these two propositions and I do not feel 100% sure about them so I was wondering if I could get any help or advice. Thank you.
99 views

### Number of pairs of rational numbers that satisfy the given relation

The number of pairs $(x,y)$ that satisfy : $2x^2 + y^2 + 2xy - 2y + 2 = 0$ is a.) $0$ b.) $1$ c.) $2$ d.) None of the foregoing numbers My attempt : I am not well versed in number theory , thus I ...
17 views

### i'm confusing on power of x in modular equation..

From question 1, i thought that fermat's little theorem. a^p≡a ≡b^p ≡ b (mod p ) and because (a,p)=1=(b,p) , (a,p^2)=1=(b,p^2), a^(p^2)≡a≡b≡b^(p^2) mod p^2 but how can we know that a^p≡b^p mod ...
409 views