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

learn more… | top users | synonyms

0
votes
0answers
5 views

Proving rigorously that if $3|(a+b)$ then $3|(a^3+b^3)$ using divisibility definition

Let $a,b\in \mathbb Z$. Prove rigorously using divisibility definition that if $3|(a+b)$ then $3|(a^3+b^3)$ After a bit of algebra I get that $$3\overset{?}{|}(a+b)^3-3ab(a+b)$$ So now how do I ...
0
votes
1answer
42 views

How many 10 digit numbers are there so the sum of the digits is $2$?

How many 10 digit numbers are there so the sum of the digits is $2$? $abcdefghij$ is the 10 digit number. By default, $a=1$ is a must. $= 1bcdefghij$ Now we need: $bcdefghij = 1$ How can I solve ...
0
votes
0answers
48 views

Using fermats last theorem in a proof

Question: If $x,y,z,n$ are natural numbers, $x,y,z,n>1$, with $x^n +y^n=z^n$ then show that $x,y,z$ are all greater than $n$ Here to prove this i would like to use Fermat's last theorem, to ...
0
votes
0answers
21 views

Sum of divisor powers?

A given number is divisible by 2, 3, and 5, and has altogether 2013 divisors. The smallest such number is $2^N \cdot 3^M \cdot 5^p$ where $N + M + P=$? I would $N + M + P = 2012$ because by a ...
0
votes
2answers
41 views

Smallest integer $x$ for which 10 divides $2^{2013} - x$

Find the smallest integer $x$ for which 10 divides $2^{2013} - x$ Obviously, $x \equiv 2^{2013} \pmod{10}$ But how can I reduce $x$?
0
votes
2answers
29 views

Why $(10^ab+c)^{4d+1}-c \mid 10$?

I came across the following equation: $$x=(10^ab+c)^{4d+1}-c$$ Why is $x$ a multiple of $10$ for any natural number values for $a$, $b$, $c$ and $d$? The only progress I made was that $a$ could be ...
4
votes
1answer
79 views

If $\frac{a+1}{b}+\frac{b}{a}$ is an integer then it is $3$.

If $\frac{a+1}{b}+\frac{b}{a}$ is an integer for positive integers $a,b$ then prove that this integer is $3$. I reduced the to prove that if $\frac{c^2+d^2+1}{cd}$ is an integer then it is $3$ where ...
0
votes
2answers
30 views

$2^{n+1}|2^{2^n}$ and $2^{2^n}+1|2^{2^{n+1}}-1$

$2^{n+1}|2^{2^n}$ and $2^{2^n}+1|2^{2^{n+1}}-1$ I have not been able to show the above. I would greatly appreciate any help.
2
votes
1answer
14 views

Deduce that the number of divisions in the Euclidean algorithm is at most $2n + 1$

Theorem. If $a > 0$ and $b$ is arbitrary, there is exactly one pair of integers $q, r$ such that the conditions $b = qa + r, 0 \leqslant r < a$, hold. Repeated application of this theorem ...
0
votes
1answer
35 views

Show that the solution for the Diophantine equation $x^2 - y^2 = N$ is unique if and only if $|N|$ or $\frac{|N|}{4}$, respectively, is $1$ or prime.

Show that the solution for the Diophantine equation $x^2 - y^2 = N$ is unique if and only if $\mid N \mid$ or $\frac{\mid N \mid}{4}$, respectively, is $1$ or prime. I have an idea of how to show ...
3
votes
1answer
31 views

Prove for any integer $N$ that there exists $n > N$ where $n!-1$ is not a prime

I was thinking about Euclid's proof of the infinitude of primes and the fact that we could make the argument about $n!-1$ instead of $n!+1$ when I wondered if it would be easy to prove that for any ...
0
votes
2answers
51 views

$\mathrm{lcm}(b,c)$ from $\mathrm{lcm}(a,b)$ and $\mathrm{lcm}(a,c)$

Given that lcm$(a,b)=60$ and lcm$(a,c)=270$, find lcm$(b,c)$ I believe you're supposed to use the rule lcm$(a,b)=p_1^{\text{max}(r_1,s_1)}\cdots p_m^{\text{max}(r_m,s_m)}$ Here's my work so far: ...
0
votes
1answer
9 views

“Multivariable” version of this lemma about showing analytically that a number is irrational.

Lemma: let $\alpha \in \mathbb{R}^+$ and $p_1,p_2,\dots, q_1, q_2, \ldots \in \mathbb{N}$ such that $\left|\alpha q_n - p_n \right| \neq 0$ for all $n \in \mathbb{N}$ and $$ \lim_{n \rightarrow ...
3
votes
1answer
57 views

Could someone take a crack at this number theory problem?

The question is stated as follows: If $\mathrm{gcd}(a,m)=1$ and $X$ is a complete residue system $\bmod m$, then the set obtained by multiplying each member of $X$ by $a$ is also a complete residue ...
1
vote
1answer
32 views

Numbers that can be represented by 32 bits

A typical computer 'word' is either 32 or 64 bits long. For each of the following encoding, determine the range of numbers (in base 10) that can be represented with (i) 32 bits and ...
0
votes
1answer
33 views

How to prove $V(5x^2+6xy+2y^2-2yz-z^2)$ is empty

Let $V/\mathbb{Q}$ be the projective variety $V:5x^2+6xy+2y^2=2yz+z^2$. I want to prove $V(\mathbb{Q})$ is empty. Given $[x,y,z]$ in $V$, WLOG assume $x,y,z\in \mathbb{Z}$ and $\gcd(x,y,z)=1$. ...
0
votes
2answers
32 views

Find the number which is the sum of different consecutive integers

Problem: Find $n$ such that $n>200$ $n$ can be written like the sum of of $5$, $6$, and $7$ consecutive integers I'm currently studying modular arithmetic so I tried to solve witusoinh it. ...
3
votes
1answer
52 views

Relationship between increasing integer sequences

Suppose that $\mathcal X\cap \mathcal Y=\emptyset$, that $\mathcal X\cup \mathcal Y=\Bbb N$ and that $X(n),\;Y(n)$ are increasing surjections $\Bbb N\to \mathcal X$ respectively $\Bbb N\to \mathcal ...
0
votes
2answers
35 views

How to solve this quartic congruence?

Given $x^4 + 36x^3 - 19x^2 + 11x - 14 \equiv 0 \pmod{5}$. How would one go about solving such an congruence equation? Maybe it's possible to reduce this to a quadratic congruence? I can't figure it ...
1
vote
2answers
36 views

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$

Let $t_n$ denote the $n$th triangular number. For what values of $n$ does $t_n$ divide $t_1^2+t_2^2+ \cdots +t_n^2$. The hint says that because $t_1^2+t_2^2+ \cdots +t_n^2 = t_n(3n^3 + 12n^2 + 13n + ...
1
vote
2answers
34 views

Criteria for the existence of zero-divisors and idempotent elements in the integers modulo $n$

I need help in establishing or at least deciding the validity of the following two criteria: There are in the ring $Z_n$ non-trivial zero divisors if only if $n$ is divisible with some square. ...
7
votes
4answers
67 views

Proof: if p is prime, and 0<k<p then p divides ${p \choose k}$

Question : IF p is prime, and 0< k< p show that $ p | {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)... (p-(k-1))(p-k)! \over (p-k)! k(k-1)(k-2)...3.2.1}$$ Now the (p-k)! ...
1
vote
4answers
69 views

Solve $3x \equiv 17 \pmod{2014}$

Solve $$3x \equiv 17 \pmod{2014}$$ So first I suppose $3^{-1} \pmod{2014}$ $2014 = 671(3) + 1 \implies 1 = 2014 - 671(3)$ But this gives $3^{-1} = 1 \pmod{2014}$ which is incorrect?
0
votes
3answers
27 views

Find the Inverse Modulus using Euclid's algorithm

I asked this before, but unfortunately, I didnt know the methods, nor was the questions phrased properly. Find the inverse of $4258 \pmod{147}$ Using Euclidean Extended Algorithm. Begin By Stating ...
4
votes
4answers
225 views

Find how many positive divisors a number has. What would you do?

Recently I learned an amazing thing. Suppose you are given a number and you have to find how many positive divisors it has. What would you do ? Solution: Suppose you select $12$. It has ...
1
vote
3answers
32 views

Solve diophantine equation using modular arithemtic

Solve for integers, $x, y$ $4258x+147y=369 \implies 4258x \equiv 369 \pmod{147}$ I got this question from SE, but I want to try this approach. I suppose we will find the inverse modulus of $4258 ...
1
vote
3answers
57 views

Last 2 digits of $2345^{369}$

http://i.stack.imgur.com/hte3J.jpg This webpage says last 2 digits of $2345^{369}$ is $75$. But considering only last 2 digits: $45^1 = 45$ $45^2 = 25$ $45^3 = 25$ The last 2 digits are always ...
1
vote
3answers
26 views

Can I conclude there's no $x/y$ such that $(x/y)^2=-1$ mod 3

Suppose $x^2+y^2=0$ mod 3. I want to show 3 divides $x$ and $y$. Assume $(y^2,3)=1$. Dividing $y^2$ gives $(x/y)^2=-1$ mod 3. Here I want to use the fact that $-1$ is not congruent to any square mod ...
0
votes
2answers
32 views

Show if $k$ is an integer, then $\sqrt[n]{k}$ is rational if and only if it is an integer.

$(i)$ Show that if the reduced fraction $a/b$ is a root of the equation $c_0x^n + c_1x^{n-1} + \cdots + c_n = 0, $ where $x \in \mathbb{R}$ and $c_0,\ldots,c_n \in \mathbb{Z}$ with $c_0 \ne 0$, ...
7
votes
3answers
354 views

Finding the number of divisors of a number?

How can I find the number of divisors of $2011\times2012\times2013\times2014+1$?
1
vote
0answers
36 views

Do you know any answer for equation y^2 = x^3 + k? [duplicate]

As you know, the equation y^2 = x^3 + k for k like (4n-1)^3 - 4m^2 that m , n are integers & no prime number that p is congruent to 1 modulo 4 count m, don't have any answer & it's proof is by ...
0
votes
0answers
16 views

Can a simple prime product be decoupled using only one variable using a computer algorithm?

Let $P(x) = D(x) + m(x)$ and $Q(x) = D(x) - m(x)$ where $D(x) = \sqrt{N} \cosh x$ $m(x) = \sqrt{N} \sinh x$ where $N = PQ =$ a prime product, and $P(x_0)$ and $Q(x_0)$ are prime number ...
2
votes
2answers
77 views

How do I solve this Olympiad question with floor functions?

Emmy is playing with a calculator. She enters an integer, and takes its square root. Then she repeats the process with the integer part of the answer. After the third repetition, the integer part ...
3
votes
0answers
41 views

At most one divisor in $[\sqrt{n},\sqrt{n}+\sqrt[4]{n}]$

In one math book I'm reading there was the following problem, given as an exercise: For any $n\in\Bbb N$ there is at most one divisor of $n$ in the interval $[\sqrt{n},\sqrt{n}+\sqrt[4]{n}]$. I ...
1
vote
1answer
28 views

Solving the Diophantine equation $ax + by = c$ using Maple [on hold]

I wrote a program in Maple called EEAsolve (I'm not sure how I can show everybody the code), and what it does is takes 3 parameters from $ax + by = c$: $a$, $b$, and $c$. When I run the program with ...
0
votes
0answers
20 views

Fermat Numbers are Prime Proof [duplicate]

Assume that the Fermat numbers $F_m$ are pairwise relatively prime. Prove from this that there are infinitely many primes. My proof can only involve that the Fermat numbers are pairwise relatively ...
2
votes
3answers
41 views

Prove that for any natural number $n$ there exists a prime number $p$ greater than $n$

Prove that for any natural number n there exists a natural prime number p , such that $ p>n $. How can I prove that ? Thank you.
1
vote
1answer
60 views

Four different positive integers a, b, c, and d are such that $a^2 + b^2 = c^2 + d^2$

Four different positive integers $a, b, c$, and $d$ are such that $a^2 + b^2 = c^2 + d^2$ What is the smallest possible value of $abcd$? I just need a few hints, nothing else. How should I begin? ...
1
vote
0answers
50 views

Can anyone solve this without substitution

Find the values of $k \in \mathbb{Z}$ so that $\frac{234k}{641}$ has remainder $1$. Can anyone solve this without substitution?
9
votes
3answers
108 views

Prove that $a+b$ cant divide $a^a+b^b$ nor $a^b+b^a$

Let a and b be natural numbers so that $2a-1,2b-1$ and $a+b$ are prime numbers. Prove that $a+b$ cant divide $a^a+b^b$ nor $a^b+b^a$. I get that $gcd(a,b)=1$. I havent got anything special for now ...
4
votes
1answer
67 views

$A\subseteq \{1,2,3, \ldots 2000\}, $ and for any $a,b\in A,\; |a-b|$ is not equal to 4 or 7,

$A\subseteq \{1,2,3,\ldots2000\}$, and for any $a,b\in A,$ $|a-b|$ is not equal to 4 or 7. Then, at most, how many element does $A$ contain? For general condition,$|a-b|$ is not equal to $i$ or $j, ...
0
votes
0answers
20 views

finding the logic behind the division method of hcf [on hold]

How does the division method of finding hcf work.should we consider that their exist a common factor that divides both the numbers.
2
votes
3answers
119 views

Prove that distinct Fermat Numbers are relatively prime [duplicate]

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$. Prove that for $m \ne n$ we have $(F_m, F_n) = 1$. I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in ...
0
votes
3answers
23 views

Solving for mod indirectly

How many positive integers $n$ exist such that $\frac{680}{n}$ is an integer? So, this is quite obvious, $680 \equiv 0 \pmod{n}$ How should I solve for $n$? There will be multiple $n$?
25
votes
8answers
3k views

Is there something special about 2015?

Is there some property which is satisfied only by the number 2015 (among natural numbers, say) or is there a relatively simple question for which the answer is, surprisingly, 2015? This is inspired ...
0
votes
1answer
19 views

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$)

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$) I'm having a trouble showing this. I think I need to ...
-2
votes
1answer
24 views

Find all solutions of the linear congruence $3x-7y \equiv 11$ (mod $13$)

Find all solutions of the linear congruence $3x-7y \equiv 11$ (mod $13$) This is a problem from Burton's Elementary Number Theory. The answer says $x \equiv 11+ t, y \equiv 5+6t$ (mod 13). I don't ...
1
vote
1answer
23 views

Proving $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$

Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$ My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then ...
2
votes
2answers
120 views

If GCD of a list of numbers is 1, is it a necessary condition that GCD of at least one pair of numbers from the list should be 1?

Suppose our numbers are {2, 6, 3}. GCD (2, 6, 3) = 1, GCD (2, 6) = 2, GCD (6, 3) = 3, but GCD(2, 3) = 1 If GCD(a,b,c) = p, GCD(a,b) = q, GCD(b,c) = r, GCD(c,a) = s, is it possible that p = 1 and (q ...
2
votes
2answers
27 views

Solve diophantine using modulus

Find all pairs of positive integers $(m, n)$ that satisfy, $mn + 3m - 8n = 59$ Using Modular arithmetic. Okay, this is a diophantine equation, where can I begin?