Tagged Questions

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

1answer
165 views

Show that if $n$ is is a positive integer such that $n\ne 2$ and $n\ne 6$ then $\phi(n) \ge \sqrt n$

$\phi(n)$ being Euler's totient function. Regarding effort put into the problem: In the case that $n$ is a prime $p$, then it is given that $\phi(p) = p-1$. It is also given that $n\ne 2$, so the ...
2answers
94 views

Does $7$ divide $2 x^2 - 4y^2$ for all $x,y$?

Does $7$ divide $2 x^2 - 4y^2$ for all $x,y \in \mathbb{Z}$?
1answer
158 views

About the multiplicative order of $2$ modulo a prime

Is this true, that for all integer $n>0$, but $n=1$ and $n=6$, there exists a prime $p$ such that $n=ord_p(2)$, where $ord_p(2)$ is the multiplicative order of $2$ modulo $p$? If not, what is the ...
1answer
69 views

How to prove that all primes $p$ will have a power $p^k$ with a $2$ in its decimal representation?

How to prove that all primes $p$ will have a power $p^k$ with a $2$ in its decimal representation? This is a lemma I need to prove a problem I'm working on. My attempt: Suppose for the sake of ...
2answers
171 views

Finding the summation of the floor of the series identity

I would appreciate if somebody could help me with the following problem: Q: How to proof ? The number of positive divisors of $n$ is denoted by $d(n)$ ...
2answers
219 views

Prove that $n^7+7$ can never be a perfect square.

Prove that for a positive integer $n$, $n^7+7$ cannot be a perfect square. I managed to show that $n \equiv 5 \pmod{8}$ or $n \equiv 9 \pmod{16}$. But nothing came from that so I presume another ...
1answer
510 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
0answers
47 views

Inverse image of rationals under tangent function is free abelian?

It is easy to see that the set $\{x:\tan x\in \Bbb Q \,\, or\,\, \pm\infty\}$ forms a group under addition. It is a free abelian group?
1answer
102 views

Question about the number of primes greater than $3$ in a sequence of consecutive integers.

I recently noticed that for any $x > 16$, it follows that there are at least $2$ integers in the any sequence of 3 consecutive integers that are divisible by a prime greater than $3$. For example, ...
1answer
297 views

Elementary proof of prime number theorem?

From Wikipedia: "The prime number theorem is also equivalent to: $$lim_{x \rightarrow \infty} \frac{\psi(x)}{x}=1$$ where $$\psi(x) = \sum\limits_{n \leq x} \Lambda(n)$$ is the Chebyshev function. ...
1answer
85 views

Failing Fermat Primality Test

Consider the following algorithm: Suppose $n\geq 2$, and let FermatTest be an algorithm such that if $a^{n-1}\not\equiv 1\mod n$ then return composite. If FermatTest yields $a^{n-1}\equiv 1 \mod n$, ...
2answers
221 views