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

learn more… | top users | synonyms

3
votes
1answer
32 views

Diophantine equation involving factorial …

Question . Find all positive integer solutions to the equation below , $$(n-1)!+1=n^m$$ (i)observe that $n>1$ and $n$ is a prime number (if not we can choose a prime number $p<n$ such that $p|n$ ...
5
votes
0answers
34 views

When can $n^k+k$ be a perfect square?

For what positive integers $k$ does there exist a positive integer $n$ such that $n^k+k$ is a perfect square? Certainly for all $k$ such that $k+1$ is a perfect square, since we can substitute $n=1$. ...
3
votes
1answer
33 views

What is the discrete log used for?

Perusing Wikipedia, I stumbled on the discrete logarithm. I looks interesting that we'd be able have a function that could solve $b^k=g$ for integers $b,k,$ and $g$. However, Wikipedia says "No ...
4
votes
1answer
62 views

Is this an accurate proof that no perfect square is of the form $4k+3$? ($k$ an integer)

A positive integer $n$ is a perfect square. Prove that it cannot be of the form $4k+3$, where $k$ is an integer. I tried to prove this by proof by contradiction: if $n$ is a perfect square, then ...
1
vote
1answer
24 views

Congruence with $x$ in a power

I don't know how to find $x$ in a situation like this: $$a^x \equiv b \pmod c$$ I think I'm missing something around little fermat theorem, Could anyone help?
-1
votes
1answer
35 views

Relations between the GCD of two numbers and the GCD of their linear combinations

(a) Prove that $a|b$ if and only if $\gcd(a,b) = a$. (b) Let $b > 9a$, Show that $\gcd(a,b) = \gcd(a,b−2a)$ (c) Show that If $a$ is even and $b$ is odd, then $\gcd(a,b) = \gcd(a/2,b)$ (d) Show ...
1
vote
2answers
40 views

How prove this diophantine equation $x^2-y^2\equiv a\pmod p$ have only $p-1$roots

Question: let $a\neq 0$.and $p$ is prime numbers. show that the number of ordered two-tuples $(x,y)$such this following diophantine equation $$x^2-y^2\equiv a\pmod p$$ at most $p-1$ ...
7
votes
0answers
32 views

Divisors of sequence $n,P(n),P(P(n)),\ldots$

Let $P(x)$ be a polynomial with nonnegative integer coefficients consisting of more than one nonzero term. Let $n$ be a positive integer. Is the set of prime numbers which divide at least one number ...
5
votes
0answers
27 views

Congruence properties of $a^5+b^5+c^5+d^5+e^5=0$?

It is known that given a solution to, $$a^4+b^4+c^4 = d^4\tag1$$ then either $-c+d,\;c+d$ is always divisible by $2^{10}$. For example, $$95800^4+414560^4+217519^4=422481^4$$ then ...
2
votes
2answers
40 views

Writing number as sum of reciprocals of factorial

Given a real number $r>0$. Is there a way to determine whether $r$ can be written as a (possibly infinite) sum of distinct terms of the form $1/n!$? For example, if we want to determine whether ...
2
votes
2answers
131 views

Proof by Contradiction on prime numbers [duplicate]

Prove using contradiction that any prime number greater than $3$ is of the form $6n \pm 1$. Thanks for any help
0
votes
1answer
12 views

Rational roots of a polynomial with integral coefficients and constant term 1.

Here is the problem I am working on from Hardy "A course of Pure Mathematics." Given the polynomial with integral coefficients $x^n+p_1x^{n-1}+p_2x^{n-2} + \cdots + p_n = 0$, with $p_n=1$, and ...
1
vote
0answers
42 views

Is there a solution to $a^4+(a+d)^4+(a+2d)^4+(a+3d)^4+\dots = z^4$?

One can be familiar with, $$31^3+33^3+35^3+37^3+39^3+41^3 = 66^3\tag{1}$$ I found, $$29^4+31^4+33^4+35^4+\dots+155^4 = 96104^2\tag2$$ which has 64 addends. The equation, ...
0
votes
1answer
42 views

Find all positive integers $a,b,c,d$ with given conditions. [on hold]

Find all positive integers $a, b, c, d$ such that $$\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)\left(1+\frac{1}{d}\right)-\frac{1}{abcd}$$ is a positive integer. ...
1
vote
2answers
57 views

About the infinitude of some kind of primes? [on hold]

I will propose this proof: A Mersenne number always has the form $$2^{p}-1=4n+3$$ since for all $p≥2$ we have $$2^{p}-1≡-1(mod4)≡3(mod4)$$ The Dirichlet prime number theorem ...
2
votes
1answer
36 views

Prove that if $\{a_n\}$ is a sequence of natural numbers such that $\{ a_n^{-1}\}$ is an arithmetic sequence then all $a_i$ are equal

Prove that if $\{a_n\}$ is a sequence of natural numbers such that $\left\{\frac{1}{a_n}\right\}$ is an arithmetic sequence then all the $a_n$s are equal. I have no clue where to begin from, ...
2
votes
1answer
13 views

Sequences that misses exactly the Polygonal and the $n$-th power numbers

Can you give an example any such sequence $u_n$ such that it misses exactly the Polygonal Numbers, say for example misses exactly the Pentagonal Numbers and so on? Can you give an example any such ...
1
vote
1answer
18 views

Are Primitive Dirichlet Characters linearly independent.

For a positive integer $N$, let $$S_N=\{ \chi~\mid~ \chi \text{ is primitive Dirichlet characters modulo }F,\text{ where } F\mid N \}.$$ I want to check the Linear independence on $S_N$. More ...
0
votes
3answers
65 views

How do I prove that $x^2 ≡ 3 \mod4$ has no solutions? [on hold]

The congruence $x^2 ≡ 3 \mod4$ has no solutions. How do we prove that it has no solutions?
3
votes
4answers
80 views

More rigorous method for this elementary problem?

The problem is: Find all real values of $x$ such that $$(5+2\sqrt{6})^x+(5-2\sqrt{6})^x=2\sqrt{3}$$ One solution I received was as follows: $5+2\sqrt{6}$ can be expressed as ...
0
votes
1answer
20 views

How to get the maximum and minimum number of length $m$ and the sum of the digits $s$

How to get the maximum and minimum of length $m$ and the sum of the digits $s$ By example: Length: 2 Sum of its digits: 15 Max: 96, Min: 69 Length: 2 Sum of its digits: 2 Max: 20, Min: 11
2
votes
2answers
40 views

When is a number square in Galois field p^n if it's not square mod p?

Here is the problem, that I'm stuck on. There is no square root of $a$ in $\mathbb{Z}_p$. Is there square root of $a$ in $GF(p^n)$? Well, it's certainly true that $$x^{p^n}=x$$ and $$x^{p^n-1}=1$$ ...
1
vote
4answers
71 views

How many cube roots does 1 have modulo 162?

How many cube roots does $1$ have modulo $162$ this is equivalent to saying how many solutions to $x^3 \equiv 1 $ mod$162$ all my attempts are leading a dead end any help appreciated the fact that ...
2
votes
1answer
31 views

Find $x$ such that $x \equiv7\pmod {37}$ and $x^2 \equiv 12\pmod {37^2}$

Find $x$ such that $x \equiv7 \pmod {37}$ and $x^2 \equiv 12\pmod {37^2})$ My attempt: Given $x \equiv7\pmod {37}$ so $37|(x-7)$ so $37^2|(x-7)^2$ so $x^2-14x+49 \equiv 0\pmod {37^2}$ as ...
1
vote
2answers
37 views

How to prove $x^{\phi(m)+1}\equiv x\pmod{p}$ [duplicate]

How do I prove that $x^{\phi(m)+1}\equiv x\pmod{p}$ when $m=pq$, two distinct primes? I kind of have an idea that it involves Euler's Theorem but it doesn't seem to be working as well as I wanted it ...
15
votes
1answer
69 views

Showing $\left(a + \frac{1}{2}\right)^N + \left(b + \frac{1}{2}\right)^N \in \mathbb{Z}$ for finite amount of natural numbers $N$

If $a$ and $b$ are positive integers, how would I go about showing that$$\left(a + \frac{1}{2}\right)^N + \left(b + \frac{1}{2}\right)^N \in \mathbb Z $$ for only a finite amount of natural numbers ...
1
vote
2answers
46 views

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod {73}$

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod{73}$. It is clear that an attempt to write this out as $90x-41=73n,\exists n\in \mathbb{Z}$ won't be very ...
7
votes
1answer
82 views

Simple Question On Relationship Between Cubes And Squares

I'm new to this number theory business, not to mention terribly naive. I wonder whether someone could explain the technique (assuming there is one) to show whether the expression $12C - 3$ (where ...
1
vote
1answer
20 views

Proving the asymptotic behavior of the prime counting function (Prop 2.1 in Ch.7 Princeton Lectures in Analysis-Complex Analysis)

This is taken from Complex Analysis by Elias M. Stein and Rami Shakarchi. $\psi(x) \text{ is Tchebychev’s ψ-function defined by}$ $$\psi(x)=\sum_{p^m\leq x} \text{log }$$ the sum is taken over the ...
3
votes
0answers
30 views

Partial sums of exponential series as a reduced fraction

The partial sum of the exponential series can be written as $$ \sum_{k=0}^n\frac{1}{k!} = \frac{nt+1}{n!} $$ When is this fraction a reduced fraction? More precisely, when does the reduced form of ...
0
votes
1answer
19 views

Factorization with a Primitive Factor of Polynomials

Question: Let $f,g\in\Bbb Q[x]$. Why is it that $\rm\color{#c00}{(1)}$ if $f$ is monic then $f=\frac{1}{a}f^*$ for some primitive polynomial $f^*\in\Bbb Z[x]$ and $a\in\Bbb Z$ ? ...
0
votes
2answers
45 views

Find the remainder if $19^{55}$ is divided by 13.

The question, as stated in the title, is Find the remainder if $19^{55}$ is divided by 13. Here is my approach for solving this problem. I know that $19\equiv6$ (mod 13), so $19^{55}\equiv ...
3
votes
2answers
64 views

How many numbers less than $x$ have a prime factor that is not $2$ or $3$

I am trying to figure out the number of integers greater than $1$ and less than or equal to $x$ that have a prime factor other than $2$ or $3$. For example, there are only two such integer less than ...
7
votes
1answer
76 views

Divisors of sequence $1!+2!+\ldots+n!$

Is the set of prime numbers which divide at least one number in the sequence $a_n=1!+2!+\ldots+n!$ finite or infinite? I try to show that it's infinite. Suppose the set is finite and consists of ...
5
votes
0answers
86 views

A set of 19 numbers that are at most 93, and a set of 93 numbers that are at most 19, have equal sumsets [on hold]

If $x_1, x_2, ..., x_{19}$ are natural numbers lower or equal than 93 and $y_1, y_2, ..., y_{93}$ are natural numbers lower or equal than 19 then there is a non zero sum of some $x_i$ which is equal ...
2
votes
3answers
95 views

Show that $\lim_{n\rightarrow\infty}{\displaystyle\sum_{i=1}^{n}{\frac{F_n}{2^n}}}=2$

I need help to show that $\lim_{n\rightarrow\infty}{\displaystyle\sum_{i=1}^{n}{\frac{F_n}{2^n}}}=2$, where $F_n$ is the n-th number in the Fibonacci sequence. I know how to prove this by putting ...
0
votes
1answer
42 views

Find conditions on $m$ and $n$ that ensure that $f$ is a bijection.

Given: $X=\{0,1,2,...,m-1\}$, $f:X\to X$, $f(x)=nx \pmod m$. Find conditions on $m$ and $n$ that ensure that $f$ is a bijection. Progress It seems that $(m,n)=1$ but I can't prove that. I tried ...
2
votes
1answer
53 views

Prove Euler's Theorem when the integers are not relatively prime

How can I prove Euler's Theorem: $$x^{\phi(m)+1} \equiv x \pmod m$$ is still true when $x$ is not relatively prime to $m$? Edit: when m=pq where p and q are distinct primes
12
votes
1answer
495 views

Can this interesting property be proven?

$$2^2+3^2+5^2+7^2+9^2+11^2=(17)^2$$ $$22^2+33^2+55^2+77^2+99^2+11^2=(143)^2$$ Also: $$22^2+33^2+55^2+77^2+99^2+121^2=(187)^2$$ $$222^2+333^2+555^2+777^2+999^2+1221^2=(1887)^2$$ ...
1
vote
1answer
20 views

A possible defining characteristic of primitive roots.

If $n$ is a primitive root $\bmod p$ ($p$ is an odd prime ) does there always exist a least residue $t$ such that $n^t \equiv t \pmod p$ ?
2
votes
1answer
36 views

How many distinct values of floor(N/i) exists for i=1 to N.

Say we have a function $F(i)=\text{floor}(N/i)$. Then how many distinct values of $F(i)$ will exist for all $0 \leq i \leq N$ e.g. We have $N=25$ then. $F(1)=25$ $F(2)=12$ $F(3)=8$ $F(4)=6$ ...
1
vote
2answers
51 views

Notation question: $\ll$

I was perusing http://mathworld.wolfram.com/HighlyCompositeNumber.html and saw the following at the end: Nicholas proved that there exists a constant $c_2>0$ such that $Q(x) \ll (\ln x)^{c_2}$. ...
1
vote
1answer
18 views

Cubic residues over $\mathbb{Z}_{p^2}^{*}$

Definition: $x\in\mathbb{Z}_{n}^{*}$ is a cubic residue if there exists $y\in\mathbb{Z}_{n}^{*}$ s.t. $y^3\equiv x \pmod{n}$. I have been asked to prove (and I already did) that if $n=pq$, ...
2
votes
1answer
20 views

Discrete logarithm when $\alpha$ is not a primitve root

When a number $\alpha$ is a primitive root for a prime number $n$ then $\beta \equiv \alpha^{x} \mod n$ can be written as $x = \log_\alpha(\beta) \mod n-1 $. If $n$ is not a prime, the equation ...
3
votes
3answers
44 views

Primitive roots of $25$

I'm kind of struggling with the concept of primitive roots with non primes, specifically for $25$ in this case. I was calculating the sequences $2^x \pmod {25}$ and $3^x \pmod{ 25}$ for each $x$ up to ...
11
votes
2answers
442 views

(Non?)-uniqueness of sums of squares

(I've had almost no exposure to number theory, so please keep answers as elementary as possible.) Write $\mathbb{N} = \{0,1,2,3,\ldots\}$ for the natural numbers. Then every element of $\mathbb{N}$ ...
-6
votes
1answer
61 views

Prove that $(a+b)/c = a/c + b/c$. [on hold]

Prove that one can simplify a fraction to get a number and a fraction. I know this is obvious intuitively, but I'd like to see a formal proof. Thanks!
8
votes
0answers
41 views

Dividing first $n$ primes into two sets with equal sum

Let $N$ be a positive integer. Does there always exist $n>N$ such that the first $n$ primes can be divided into two sets with equal sum? If $n$ is even, the sum of the first $n$ primes is odd, so ...
8
votes
1answer
175 views

How to solve $y^2=3x^4+3x^2+1$ for integers.

If $x,y \in \mathbb Z$ , then find all the solutions of $$y^2=3x^4+3x^2+1$$ I was asked this question by my friend who said that he encountered this while solving another problem. I have ...
10
votes
1answer
28 views

Find all positive integers $n$ such that $\phi(n) + \tau(n) > n$. [duplicate]

How do I find all positive integers $n$ such that $\phi(n) + \tau(n) > n$? I attempted using the formulas for $\phi(n)$ and $\tau(n)$, but I feel this approach is kind of handwavy...