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

learn more… | top users | synonyms (1)

2
votes
7answers
157 views

Prove by induction that $n(n+1)(n+5)$ is multiple of 3

$$n(n+1)(n+5) = 3d$$ I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be ...
3
votes
0answers
180 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
1
vote
1answer
12 views

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$.

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$. So far I have shown that, if $gcd(a,n)=1$, then $gcd(a^j,n)=1$. I also have a ...
0
votes
4answers
61 views

Prove that for all integers $a$ and $b$ that $a + b$ and $a − b$ are either both odd or both even.

Prove that for all integers $a$ and $b$ that $a + b$ and $a − b$ are either both odd or both even. Stumped on this proof. I've only been able to figure it out assuming that both a and b are even: ...
6
votes
3answers
915 views

How many ways are there to write $675$ as a difference of two squares?

How many ways are there to write the number $675$ as a difference of two squares? Is there a way to generalize this?
2
votes
2answers
53 views

Simple proof that $a$ is coprime

Prove that if $a$ divides $x^n-1$ and $x^m-1$, then $a$ is coprime with $x$. I think this should be easy but I can't think of a way to do it.
7
votes
2answers
147 views

$\gcd(a,b)$ compared to $\gcd(3a,b)$

$\gcd(a,b)=\gcd(3a,b)$? They are obviously not equal in general, as $\gcd(ax, bx)=|x|\gcd(a,b)$.
1
vote
2answers
545 views

Lucas Numbers Proof $L_n = \alpha^n + \beta^n$

Proof by Induction: Lucas numbers are recursively defined as: $L_n = L_{n-1} + L_{n-2}$ where $L_1 = 1$ and $ L_2 = 3 $for $n \ge 3$ Show that: $L_n = \alpha^n + \beta^n$ for $\alpha = ...
2
votes
0answers
17 views

$ab$ is a quadratic residue modulo $c$, and $-ab$ is a QR modulo $c^{(p-1)/2}$

Given three nonzero integers, $a,b,c$. If $ab$ is a quadratic residue modulo $c$ and $-ab$ is a quadratic residue modulo $c^{(p-1)/2}$ for a fixed odd prime $p$, what can be said about $a,b,c,$ or ...
2
votes
1answer
62 views

Show that the equality is true

If $f$ is a Completely multiplicative function and $g$ is an arithmetic function such as $g(1) \neq 0$ prove that: $$(f\cdot g)^{-1} = f\cdot g^{-1}$$ Any function with the -1 as exponent is the ...
0
votes
1answer
181 views

Finding which base number given operations

$$ (35_a + 24_a) * 21_a = 1081_a $$ Which base is the above number? Any advice on how to solve questions like these? I tried making it in to a polynomial: $(3a+5 + 2a+4) * (2a+1) = 108a + 1$ ...
2
votes
1answer
42 views

How to show this equality

If $f$ is a multiplicative function and ¨$n$¨ is a square-free positive integer. Prove that: $$f^{-1}(n) = \lambda(n)\cdot f(n)$$ where $f^{-1}$ is the dirichlet inverse and $\lambda$ is the ...
0
votes
0answers
222 views

Positive integers of sum and products

Find all pairs of positive integers $m$ and $n$ where $m<n$ such that the sum of $m$ and $n$ added to the product of $m$ and $n$ is equal to $2014$ I just thought about this question and ...
0
votes
3answers
143 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
0
votes
2answers
90 views

Pair of positive integers in product sums

I am still not sure on this answer. I would like someone to help me see the solution to his question. I was working on it for a while and it is the only question that I looked at that I can not ...
4
votes
3answers
201 views

A conjecture on products/composition of Pell forms

Based on a few brute-force calculations, I've formulated the following. Conjecture. Let $x,y,u,v,p,q,a,b,c \ge 2$ be integers such that $$ (x^2+ay^2)(u^2+bv^2) = p^2+cq^2, $$ and write \begin{align} ...
1
vote
4answers
82 views

Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$

I have no idea where to start. Any hint(s) or suggestions? Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$
3
votes
3answers
73 views

Unique element m in N

Let $0 < x$. Show that there is a unique $m \in \mathbb{N}$ such that $m-1 \leq x < m$. Hint: Consider the set $\{ n \in \mathbb{N} : x < n\}$ and use the well-ordering of $\mathbb{N}$. The ...
1
vote
1answer
95 views

Pell's equation for n=2

If know that $x=3$, $y=2$ is a solution of $$x^2-2y^2=1,$$ then apparently all other solutions can be calculated as $$x_k+y_k\sqrt{2}=(x+y\sqrt{2})^k,$$ which I have trouble understanding. I've been ...
4
votes
1answer
98 views

Is it true that the gcd of cubes is the cube of gcd?

Is it true that $\forall a,b\in \mathbb{Z}$, $\gcd(a^3, b^3)=\gcd(a,b)^3$? I cannot find a counterexample, nor have I been able to finish a proof. One thing I tried was: $\gcd(a^3, b^3)= \gcd(a^3, ...
1
vote
2answers
67 views

Divisors of numbers of the form $a^2+2b^2$ with $\gcd(a,b)=1$

Let's say I have a number $n$ which can be written as $a^2+2b^2$ for integers $a,b$. By Fermat/Euler/etc., I know that the primes dividing the squarefree kernel of $n$ cannot be congruent to $5$ or ...
1
vote
1answer
46 views

Rational solutions to a system of equations

I have a system of equations $$\begin{align} xy + 3zw = 0; \\ xz + 2yw = 0; \\ xw + yz = 0. \\ \end{align}$$ Plugging it into a CAS, I see that all the rational solutions to this system have ...
0
votes
1answer
72 views

Number of Lattice Points in a Triangle

Problem Let the co-ordinates of the vertices of the $\triangle OAB$ be $O(1,1)$, $A(\frac{a+1}{2},1)$ and $B(\frac{a+1}{2},\frac{b+1}{2})$ where $a$ and $b$ are mutually prime odd integers, ...
0
votes
1answer
36 views

if $k>1$, Does $a+b =k(ax+by)$ have finitely many solutions?

Let $a,b,k,x,y$ be non-zero integers, solve $a+b=k(ax+by)$. It's a rather simple problem, but I just want to make sure that I have got all the possible solutions.
1
vote
1answer
76 views

Finding pair of integers with given modulo

Given integer Goal and S = { X0, X1, ...., Xn } where Xi is a positive integer > 1, find a, b, in S and positive integer n (not necessarily in S) such that: a*n mod b = Goal E.g. Goal = 1, S = {3, ...
0
votes
1answer
41 views

Form of solutions of Diophantine equation

Consider the following Diophantine equation $$zx^2 +xy^2 +yz^2 =xyzt .$$ Is that true that all solutions of this equation are of the form $(x,y,z,t) =(a^2 b ,b^2 c ,c^2 a ,t)$ for some ...
29
votes
8answers
3k views

Are Mersenne prime exponents always odd?

I have been researching Mersenne primes so I can write a program that finds them. A Mersenne prime looks like $2^n-1$. When calculating them, I have noticed that the $n$ value always appears to be ...
0
votes
2answers
383 views

On proving quadratic residues have 4 square roots

I'm trying to write up a proof of "if a is a quadratic residue modulo N then it has 4 separate square roots". N is the product of two primes and I have to consider the multiplicative group of the ...
2
votes
4answers
87 views

How to show that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ [duplicate]

set $ n, n \in \mathbb{N}$ and prove that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ ¨I have tried this¨ If $n > 1$ then $n = p_{1}^{\alpha_{1}}\cdot p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ ...
2
votes
1answer
51 views

Divergence of a series containing primes

Is there an easy proof showing that the series $1/p$, where $p$ changes over prime numbers, is divergent?
1
vote
1answer
117 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
0
votes
1answer
34 views

Question about spectrum versus spectral sequences

What is the difference between spectrum sequences and spectral sequences? Are they considered to be the same? I know that the spectrum sequence of a real number $\alpha$ is the sequence that has ...
2
votes
1answer
69 views

p-adic numbers and GCD

Given two numbers $a,b \in \mathbb{Z}$, how do we prove that the $p$-adic number of $\gcd(a,b)$ is the same as the minimum for the $p$-adic number of $a$ and the $p$-adic number of $b$? Does this ...
0
votes
1answer
111 views

Find the last two digits of a number

Let $x_1 = 9$ and the n-th term of the sequence is generated by this rule $\ x_n = 9^{x_{n - 1} } \ $. Task : Find the last two digits of the number $\ x_{2013} \ $. I already solved the ...
0
votes
1answer
34 views

Prove that there are infinitely many primes of form $2kp+1$ where $p$ is an odd prime

Prove that there are infinitely many primes of form $2kp+1$ where $p$ is an odd prime Suppose there are only finitely many primes of form $2kp+1$ : $$p_1,p_2,\cdots, p_r$$ I am trying to mimic ...
2
votes
4answers
103 views

Palindrome numbers with conditions

If $n$ is a palindrome of three digits and $n+32$ is palindrome of four digits then find $n$.
2
votes
6answers
288 views

Show that ${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$ [duplicate]

Show $${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$$ A hint is given to consider the expansion $(x-y)^n$ However, when I plug in a number for $n$, I don't get an ...
5
votes
1answer
84 views

Foundational proof for Mersenne primes

I know how to prove that, if $2^n-1$ is prime and $n>1$, then $n$ is prime. But how do we prove that, if $a^n-1$ is prime and $n>1$, then $a$ must equal 2?
0
votes
2answers
328 views

How to conjecture a formula of a sequence

I am trying to conjecture a formula for the $n$th term of $\{a_n\}$ if the first ten terms of the sequence are as follows 1.) $$2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366$$ 2.) $$1, 1, 0, 1, ...
0
votes
1answer
34 views

Question about greatest integer function

I'm trying to prove that $[x+y] \geq [x]+[y]$ This is my work so far: Let $x,y \in \Bbb {R}$ and suppose that $\{x\}=x-[x]$ and $\{y\}=y-[y]$, based on the definition. So then $x=[x]+\{x\}$ and ...
0
votes
1answer
27 views

Whole number and rational number relationship

Find all integer $ n $ such that$\frac {2n+3}{n-2}$ is a whole number. I expressed the numerator as $2n-4+3+4$=$2 (n-2)+7$ Then the given expression reduces to $2+\frac {7}{n-2}$ . I got $ n=1$ $n=3$ ...
25
votes
2answers
6k views

Demonstration that 0 = 1 [duplicate]

I have been proposed this enigma, but can't solve it. So here it is: $$\begin{align} e^{2 \pi i n} &= 1 \quad \forall n \in \mathbb{N} && (\times e) \tag{0} \\ e^{2 \pi i n + 1} &= e ...
2
votes
3answers
95 views

Maximum value of $a+b$ given that $\frac{1}{a} + \frac{1}{b} = \frac{1}{20}$

What is the maximum value of $a+b$ given that $\frac{1}{a} + \frac{1}{b} = \frac{1}{20}$ here $a,b \in \mathbb{Z^+}$? What I have gotten so far: From the above, $\frac{a+b}{ab} = ...
0
votes
1answer
25 views

Cardinality of the set $A=\left\{\frac{z_x}{z_y}: 1\le z_x \le N_x \text{ and } 1\le z_y \le N_y \right\}$

Cardinality of the set $A=\left\{\frac{z_x}{z_y}: 1\le z_x \le N_x \text{ and } 1\le z_y \le N_y \right\}$ where $z_x,z_y \in \mathbb{Z}$. Basically, the question is how many different fraction can ...
3
votes
1answer
105 views

Any $p + 1$ consecutive integers contain at least two invertible elements modulo $p!!$ if $p$ is odd

I am trying to prove the following: $p + 1$ consecutive integers contain at least two invertible elements modulo $m = 3 \cdot 5 \cdots ( p - 2 ) \cdot p$, where $p$ is odd. I shared my idea ...
2
votes
4answers
79 views

If $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$

I came across this problem in my number theory text and am having a bit of trouble with it: Prove if $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$. Here's what I have so far: If $c\mid ab$, then ...
1
vote
2answers
48 views

Show that the odd prime divisors of $n^2+n+1$ are of form $6k+1$ (exclude 3)

Show that the odd prime divisors of $n^2+n+1$ are of form $6k+1$ (exclude 3) I have started like below: $n^2+n+1\equiv 0 \pmod {p_i}$ $(n+1)^2\equiv n \pmod {p_i}$ Any hints/help on how to ...
3
votes
0answers
68 views

Show that the odd prime divisors of $n^2+1$ are of form $4k+1$

Show that the odd prime divisors of $n^2+1$ are of form $4k+1$ I have below so far $n^2 + 1 \equiv 0 \mod p_i$ $n^4 \equiv 1 \mod p_i$ $4 \mid \phi(p_i)$ I am not sure where to go from here. ...
0
votes
3answers
205 views

Sum of greatest integer functions question

I need to prove that $[x+y] \leq [x] +[y]+1$ I started by supposing that $[x]=m$ and $[y]=n$, where $m,n \in \Bbb {Z}$. So then that would mean that $m \leq x < m+1$ and $n \leq y < n+1$ But ...
2
votes
1answer
77 views

GCD of $a+b$ and $\frac{a^p + b^p}{a+b}$ [duplicate]

In Ivan Niven's book on "Introduction to the theory of numbers", there is a question in the first chapter that has been boggling me. Given $p$ is an odd prime and $(a,b) = 1$ where $(a,b) = ...