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

learn more… | top users | synonyms

2
votes
2answers
26 views

Can someone help me prove that $\tau(n)$ is odd [duplicate]

Can someone help me prove that $\tau(n)$ is odd if and only if $n$ is a perfect square. So basically I have to prove that $\tau(n)$ is odd iff $n = k^2$ for some integer $k$.
0
votes
1answer
30 views

My proof that there are primitive roots modulo $p^2$

Let $p$ be a prime number. I'd like to prove that there are primitive roots modulo $p^2$. Could someone check this argument? Note that if $r\in\mathbb Z$ is a primitive root modulo $p^2$, it must ...
1
vote
4answers
62 views

Show that if $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$.

Show that if $m$ and $n$ are integers such that $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$. I am not sure where to begin.
2
votes
5answers
125 views

Prove that $2^{3^n} + 1$ is divisible by 9, for $n\ge1$

Prove that $2^{3^n} + 1$ can be divided by $9$ for $n\ge 1$. Work of OP: The thing is I have no idea, everything I tried ended up on nothing. Third party commentary: Standard ideas to attack ...
0
votes
2answers
24 views

Congruence with additional conditions. [closed]

Let $$\left(ac \equiv bc \pmod m\right) \wedge \left(gcd(c,m) = d\right) \implies a \equiv b \pmod {\frac{m}{d}} $$ Is it true? Why? Thanks in advance.
1
vote
2answers
43 views

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

Let $a,b\in \mathbb Z$. Prove rigorously using divisibility definition that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ After a bit of algebra I get that $$3\overset{?}{\mid}(a+b)^3-3ab(a+b)$$ So now how ...
0
votes
1answer
49 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 ...
1
vote
1answer
75 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 ...
2
votes
1answer
28 views

Solving diophantine equation $6x+9y=1050$ where $x,y \in\mathbb{N}$

I have to solve this Diophantine equation: $6x+9y=1050$, where $x,y \in\mathbb{N}$. I am not sure as to how to solve this for only the whole numbers, but I think I'm doing it right. I used the ...
0
votes
1answer
30 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
48 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
32 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 ...
5
votes
2answers
149 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
35 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
17 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
36 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
42 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
57 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
11 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
64 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
62 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
35 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
51 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
57 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
38 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
36 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. ...
8
votes
6answers
101 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
73 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
30 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
241 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
1answer
210 views

Selfy number couldn't exist?

For a positive integer $x$, let $S(x)$ denote the sum of the digits of $x$, and $l(x)$ denote the number of digits of $x$ (in base $10$). Now given a positive integer $n \ge 2$, it seems that there ...
1
vote
3answers
33 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
60 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
28 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
33 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
362 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
37 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 ...
6
votes
2answers
401 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
0
votes
0answers
21 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
82 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
51 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
33 views

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

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
21 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
42 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
67 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? ...
0
votes
0answers
58 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
113 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
2answers
82 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
24 views

finding the logic behind the division method of hcf [closed]

How does the division method of finding hcf work.should we consider that their exist a common factor that divides both the numbers.