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

learn more… | top users | synonyms (1)

0
votes
1answer
26 views

Check if sum is possible

Given a range $[L,R]$ I need to find weather a sum $S$ can be made by taking any number between this range i.e $L, L+1, L+2,\dotsc, R$ any number of times EXAMPLE: If $S=5$ and $L=2$ and $R=3$ then ...
-1
votes
1answer
75 views

Prove or disprove that if $a = bm + r$, then $\gcd(a,m) = \gcd(a,r)$

Prove or disprove that if $a = bm + r$, then $\gcd(a,m) = \gcd(a,r)$ I tried using the fact of GCD's in my calculations to get the fact that d|b and d|a-bm then try to compare that with the gcd(a,m) ...
0
votes
1answer
83 views

Greatest common divisor of $3$ numbers

Let $a,b, c$ belong to $\mathbb Z$ such that $(a,b,c) \neq (0,0,0)$. Define the [highest common factor] greatest common divisor ${\rm gcd}(a, b, c)$ to be the largest positive integer that divides $a, ...
1
vote
1answer
46 views

how to start a proof of a system of congruences

Let $a$, $b$, $m$, and $n$ be integers with $m > 0$, $n >0$, and $gcd(m,n) = 1$. Then the system $x\equiv a$ (mod n) and $x\equiv b$ (mod m) has a unique solution modulo mn. This is not the ...
0
votes
5answers
72 views

Find all integers $n$ (positive, negative, and zero) so that $n^2 + 1$ is divisible by $n + 1$.

I found $n=0, n=1, n=-2,$ and $n=-3$, but I am having trouble showing that these are the only four. I was thinking about maybe showing that no integer on the intervals $(-\infty, -3), (-3, -2), (-2, ...
0
votes
3answers
282 views

if $x^2+ax+b=0$ has an integer root, show that it divides b [duplicate]

I don't know where to start. can anyone help me please ? if $x^2+ax+b=0$ has an integer root, show that it divides b
0
votes
1answer
785 views

Complete Residue System Proof - n elements

Theorem: Let $n$ be a natural number. Every $complete$ $residue$ $system$ $modulo$ $n$ contains $n$ elements. The definition of a $complete$ $residue$ $system$ $modulo$ $n$ as given in our text: Let ...
0
votes
2answers
63 views

Is there a commonly studied number structure with “two” of a given number?

I'm wondering whether there are structures of numbers where there is intuitively "two" of a given number. I have in mind something like what is illustrated in the following example number line ...
1
vote
1answer
63 views

Show that in a ring R, if a*b=b*a=1 and a*c=1, then b=c

I have begun by showing that R is a commutative ring since the given shows that there exists an inverse of b so that a*b=1 and also that multiplication is commutative. Next I have sown that a is a ...
1
vote
2answers
110 views

In a ring with identity, prove that (-1)(-1) = 1

I would like to attempt to solve this problem on my own if someone could give me a suggestion for how to start it.
4
votes
0answers
137 views

Consider the equation $b^n=a^b$, where $a,b,n\in \mathbb{N}^{\ast}$

DISCLAIMER: This is a self-made problem, and I don't know if there's a nice solution. Hi, here's a conjecture I have for you; I'm not seeing the "simple" solution (at least for part (a)) at the ...
1
vote
1answer
85 views

Problem with Diophantine equation

Let $a,b \in \mathbb N$ be coprime. Prove that for all $n\in \mathbb N$ such that $n>ab$ there are $r,s\in \mathbb N$ such that $n=ra+sb$. I'm really stuck on this problem. I know that since ...
5
votes
4answers
230 views

Find all triples $(p; q; r)$ of primes such that $pq = r+ 1$ and $2(p ^ 2+q ^ 2) =r ^ 2 + 1$.

We have to find all triples $(p; q; r)$ of primes such that $pq = r+ 1$ and $2(p ^ 2+q ^ 2) =r ^ 2 + 1$. This question was asked in the 2013 mumbai region RMO but i could not find a solution to it. ...
5
votes
3answers
641 views

Roots of functions / polynomials

Please excuse the naivity of this question, but it is a concept that I just have not been able to grasp entirely. My question is, why are the roots of a function, or a system of polynomials so ...
0
votes
1answer
112 views

Position of 20096 in triangular array of all natural numbers

Write the set of all natural numbers in a triangular array as Find the row number and column number where $20096$ occurs. For example, $8$ occurs on row: $3$, column: $2$ Now, the upper row is ...
2
votes
1answer
1k views

Solve polynomial congruence using Hensel's lemma

Solve $x^4+2x+46 \equiv 0$ $(\mod 4375 )$ for x. . My attempt: $x^4+2x+46 \equiv 0$ $(\mod 5^47 )$ breaks down to a Chinese Remainder Problem with the 2 following congruence's': (1) $x^4+2x+46 ...
4
votes
3answers
362 views

Solving $x^p + y^p = p^z$ in positive integers $x,y,z$ and a prime $p$

The question is from Zeitz's ''The Art and Craft of Problem Solving:" Find all positive integer solutions $x,y,z,p$, with $p$ a prime, of the equation $x^p + y^p = p^z$. One thing I noticed is ...
0
votes
1answer
525 views

If $p$ is an odd prime and $a$ is a positive integer not divisible by p, then the congruence has either no solution or 2 incongruent solutions

My question is as follows: Show that if $p$ is an odd prime and $a$ is a positive integer not divisible by p, then the congruence $x^2 \equiv a \pmod{p}$ has either no solution or exactly two ...
0
votes
1answer
82 views

How to show that if $ p \equiv 1,3 \pmod 8$ then there exists a $u,v \in \mathbb Z: u^2 + 2v^2 = p$

I'm trying to show this statement: $$p \equiv 1,3 \pmod 8, \; \; \exists \; u,v \in \mathbb Z : u^2 + 2 v^2 = p.$$ I believed I proved it the other direction using the ring $\mathbb Z{\sqrt{-2}}$. ...
2
votes
2answers
120 views

How to find all solution for $x^p - x$ (mod $p$) with Fermat's Theorem?

I got a question to show that : If $p$ is prime number, then $$x^p - x \equiv x(x-1)(x-2)(x-3)\cdots (x -(p-1))\,\,\text{(mod }\,p\text{)}$$ Now I got 2 steps to show the the two polynomials ...
2
votes
5answers
81 views

A counterexample to “$k\mid n$ if and only if $k\mid n^2$”

I am looking to prove the following statement false: Let $k$ be a positive integer, then $k\mid n$ if and only if $k\mid n^2$. So I am trying to find a $k$ where this does not hold but after ...
0
votes
1answer
52 views

Determine if the function $f(x,y)=2^{x-1}\cdot(2y-1)$, where $x,y \in \mathbb N_{+}$, is injective

We have a function of two variables $f(x,y)=2^{x-1}\cdot(2y-1)$ where $x,y \in N_{+}$. Find out if function is injective and determine its value range. I don't know now how to examine if ...
2
votes
2answers
100 views

How can I show that $a^n|b^n \Rightarrow a|b$

How can I show the following $$a^n|b^n \Rightarrow a|b$$ $$a^n|b^n \Rightarrow b^n=m \cdot a^n \Rightarrow b^n=(m\cdot a^{n-1}) \cdot a\qquad(1)$$ How can I continue? Do I maybe have to suppose ...
1
vote
1answer
112 views

Primes and infinite primes of the form $29 + 72k$

can you give the validity or proof of the following statements of my observations on Primes? $(1)$ For a positive integer $k$, there exists infinitely many primes of the form $29 + 72k$. $(2)$ If the ...
2
votes
2answers
74 views

Show that 4*AB=CAB is not possible

Show that 4*AB=CAB is not possible.Each letter denotes a single digit.It could be noted that since LHS is a multiple of 4,thus RHS would also be a multiple of 4.That's all i conclude yet...
1
vote
1answer
33 views

I'm not sure if my subscripts are lining up correctly in this elementary number theoretic induction proof

First, the motivation for the below lemma is to use in a proof that every number has a unique representation in a base. My question is that when using the inductive hypothesis, I'm not sure if my ...
4
votes
8answers
1k views

Difference of consecutive cubes never divisible by 5.

This is homework from my number theory course. Since $(x+1)^3-x^3=3x^2+3x+1$ and $x^3-(x+1)^3=-3x^2-3x-1$, to say that the difference of two cubes is divisible by 5 is the same as saying that ...
0
votes
1answer
99 views

Proving $\left\lfloor n\frac{\log (b)}{\log (a)}\right\rfloor =\left\lfloor \frac{\log \left(b^n+1\right)}{\log (a)}\right\rfloor$

Inspired by this question, I'd like to know how one would go about proving the below more general equation? $$n \in \mathbb{N},\;a \in \mathbb{N},\;b \in \mathbb{N}$$ $$b^n+1 \notin ...
0
votes
2answers
67 views

Show that if $u>v$ then $(u \mod v)\le u/2$

I cannot for the life of me figure out how to prove: if $u>v$ then $(u \mod v)\le u/2$ i tried messing around with it, and tried a bunch of prime numbers. $29 \mod 17 = 12 \le 29/2$ $31 \mod 17 ...
3
votes
3answers
446 views

If the sum of two irreducible fractions is an integer, then the denominators are equal

I have to show the following:"If the sum of two irreducible fractions with positive denominators is an integer, then the denominators are equal." $$\frac{a}{b}+\frac{c}{d}=k, \text{ where k an integer ...
0
votes
1answer
26 views

Computing digits of number in another base

I would like to program a procedure to convert a number in base 10 to a set of digits in an arbitrary base. Through empirical testing I see that the procedure involves repeated mod operations and div ...
0
votes
1answer
74 views

How does $\frac{\sigma(n)}{n}$ behave as $n$ tends to infinity? [duplicate]

Is $\frac{\sigma(n)}{n}$ unbounded as n tends to infinity? ($\sigma(n)$ is sum of proper divisors of $n$)
10
votes
3answers
2k views

Proving $\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$ [duplicate]

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
0
votes
3answers
105 views

Find all solutions of equation $x^2 \equiv 2$ in $\mathbb Z/7\mathbb Z$

Find all solutions of equation $x^2 \equiv 2$ in $\Bbb Z_{7}$ I'm not sure how to do this generally so I just powered through the first $10$-$15$ possible values for $[2]$ in $\mod 7$ and I found ...
2
votes
1answer
103 views

Amicable pair sums - intriguing sexagesimal relationships

Some amicable pair sums show intriguing relationships, for example: 1) The sums of the two numbers in each of the first five pairs have a gcd of 126. 12600 is the sum of those in the fifth pair, ...
0
votes
7answers
125 views

$(a,b) = 1$ implies $a|n$ and $b|n \implies ab|n$

Prove if $(a,b) = 1$ implies $a|n$ and $b|n \implies ab|n$. I'm pretty sure this has been asked before but I cannot find anything online.... I also have no idea how to solve it, I get stuck with al = ...
1
vote
2answers
86 views

Prove that a pair of irrational numbers is the solution to a quadratic polynomial.

Suppose a, b are two irrational numbers such that ab is rational and a+b is rational. Then a, b are the solution to a quadratic polynomial with integer coeffecients.
0
votes
1answer
53 views

Showing injectivity

I'm trying to prove that the following function is injective: $$h(x) = \{y\in \mathbb{Q}\| y<x\}$$ I think I should use the fact that the rational number are dense, but I'm not sure where to ...
0
votes
1answer
83 views

Divisibility lemma: If $a \mid x$ and $b\mid y$ then $a + b \mid x + y$.

I remember reading about a divisibility lemma which says something like if $a \mid x$ and $b \mid y$ then $a + b \mid x + y$. Obviously this one isn't true, but what is the actual lemma I am thinking ...
5
votes
1answer
89 views

Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
0
votes
1answer
47 views

If $p$ and $q$ are distinct primes such that $p|c$ and $q|c$, prove that $pq|c$

If $p$ and $q$ are distinct primes such that $p|c$ and $q|c$, prove that $pq|c$ .. I start with this: if $c=pk$ and $c=qt$ then $q|pk$ and $p|qt$ but a couldn't get the solution. I need your ...
4
votes
3answers
117 views

Solve $2^x+7=y^2$ for integer $(x,y)$

How many ordered solutions $(x,y)$ are there to the equation $2^x+7=y^2$ , where $x$ and $y$ are integers? I tried taking cases for $x$ and $y$ like they are even or odd but I couldn't solve ...
8
votes
2answers
207 views

Are there examples that we know a number is a rational number but we do not know what is its numerator and denominator?

Are there examples that we know a number is a rational number but we do not know what is its numerator and denominator? In order to say clearly, this number should given by a certain formula, such as ...
13
votes
2answers
342 views

Let $p$ be prime and $(\frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$

Let $p$ be prime and $(\frac{-3}p)=1$, where $(\frac{-3}p)$ is Legendre symbol. Prove that $p$ is of the form $p=a^2+3b^2$. My progress: $(\frac{-3}p)=1 \Rightarrow$ ...
1
vote
1answer
73 views

finding least number

Question: The least number which when divided by 5, 6 , 7 and 8 leaves a remainder 3, but when divided by 9 leaves no remainder, is: solution: L.C.M. of 5, 6, 7, 8 = 840. Required number is ...
14
votes
2answers
1k views

Show that these two numbers have the same number of digits

I want to show that for $n>0$, $2^n$ and $2^n + 1$ have the same number of digits. What I did was I found that the formula for the number of digits of a number $x$ is $\left ...
4
votes
1answer
58 views

If distinct numbers $a,b,c\in\mathbb N^+$ satisfy $(a+b)(a+c)=(b+c)^2$, prove that $(b-c)^2>8(b+c)$.

If distinct numbers $a,b,c\in\mathbb N^+$ satisfy $$(a+b)(a+c)=(b+c)^2$$prove that $$(b-c)^2>8(b+c).$$ The first thing I did after I saw the problem was turning the inequality into this: ...
1
vote
1answer
65 views

Find all $n\in\mathbb N^+$ such that the sum of the digits of $5^n$ is equal to $2^n$.

Find all $n\in\mathbb N^+$ such that the sum of the digits of $5^n$ is equal to $2^n$. I've solved this, but I think the proof is a bit weird and I wonder if there's a better one. My proof: ...
2
votes
2answers
74 views

Coprime Integers Proof Check

$\gcd(a,b)=1$ if and only if there is no prime $p$ such that $p|a$ and $p|b$ Prove it. So I went about doing it through contradiction: If $p|a$ and $p|b$ then $p|(x_{1})(x_{2})(x_{3})...$ where ...
1
vote
1answer
66 views

Relation between positive integers greater than 2

$x_1, x_2,\ldots, x_{96}$ are positive integers greater than 2, which satisfy the relation: $$ \frac{1}{x_1^4}+\frac{1}{x_2^4}+\cdots+\frac{1}{x_{96}^4}=\frac{1}{6}$$ I have two questions: 1. At least ...