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

learn more… | top users | synonyms (1)

0
votes
2answers
74 views

If $n>1$ is an integer and $0<x\le n$ and $0<y\le n$, Prove that the equation $x^n+y^n=z^n$ has no solution.

If $n>1$ is an integer and $0<x\le n$ and $0<y\le n$, Prove that the equation $x^n+y^n=z^n$ has no solution. My work: This is obvious for integers by Fermat's Last Theorem. I also think that ...
1
vote
1answer
59 views

For given positive integers $n,k$ prove that there always exists some positive integer $x$ for which $2^n\mid \dfrac{x(x+1)}{2}-k$

For given positive integers $n,k$ prove that there always exists some $x$ for which $2^n \mid \dfrac{x(x+1)}{2}-k.$ My work: $\dfrac{x(x+1)}{2}$ is the sum of all positive integers upto $x$. Now, ...
1
vote
2answers
418 views

Does the Extended Euclidean Algorithm always return the smallest coefficients of Bézout's identity?

Bezout's identity says that there are integers $x$ and $y$ such that $ax + by = gcd(a, b)$ and the Extended Euclidean Algorithm finds a particular solution. For instance, $333\cdot-83 + 1728\cdot16 = ...
0
votes
1answer
42 views

$\operatorname{GCD} (a^2, a*b, b^2)$ where $a$ and $b$ are integers

How can we find $\operatorname{GCD} (a^2, a\cdot b, b^2)$ where $a$ and $b$ are integers? I have only a slight idea of how to solve this, any help would be greatly appreciated. Thanks
0
votes
0answers
54 views

Alternative Bijection from $\mathbb{N}$ to its finite subsets

There are different proofs for the fact that there's a bijection from $\mathbb{N}$ to the set of all its finite subsets, but I would like to know if this explicit bijection does work, too. ...
2
votes
1answer
55 views

Number of factors of summation

Let $a(n)$ be the number of $1$'s in the binary expansion of $n$. If $n$ is a positive integer, show that $$\Bigg|\sum_{k=0}^{2^n-1}(-1)^{a(k)}\times 2^k\Bigg|$$ has at least $n!$ divisors. I think ...
3
votes
2answers
45 views

$(2^a -1)(2^b -1)=2^{2^c}+1$ has no nonnegative integer solutions

$(2^a -1)(2^b -1)=2^{2^c}+1$ is not possible for a,b,c nonnegative integers. Any solutions using parity Approach: $(2^a -1)(2^b -1)=2^{2^c}+1\Rightarrow$ $2^{a+b}-2^a-2^b=2^{2^c}\Rightarrow$
0
votes
1answer
40 views

$\frac{2}{\frac{a}{x}+\frac{b}{y}}\leq ax+by$

$\frac{2}{\frac{a}{x}+\frac{b}{y}}\leq ax+by$, where a+b=1 and $a,b,x,y>0$ real numbers. Any hints? part (a) was showing $\frac{2}{\frac{1}{x}+\frac{1}{y}}\leq \sqrt{xy}\leq \frac{x+y}{2}$. To ...
4
votes
1answer
127 views

Do there exist 4 rationals satisfying $a^2+b^2+c^2+d^2=1$ and $2a+b+c+d=0$?

Does there exist 4 rationals $(a,b,c,d)$ which satisfy the following two relations?, $a^2+b^2+c^2+d^2=1$ and $2a+b+c+d=0$? I spend a lot o' time with it and tried the criteria of quadratic ...
2
votes
0answers
79 views

$\frac{ra}{p} + \frac{rb}{p} + \frac{rc}{p} + \frac{rd}{p} = 2 $, with $p$ prime

Let $p>2$ be a prime and let $a$, $b$, $c$, $d$ be integers not divisible by $p$, such that $\{\frac{ra}{p}\} + \{\frac{rb}{p}\} + \{\frac{rc}{p}\} + \{\frac{rd}{p}\} = 2 $ for any integer $r$ not ...
15
votes
1answer
557 views

Prove that the product of some numbers between perfect squares is $2k^2$

Here's a question I've recently come up with: Prove that for every natural $x$, we can find arbitrary number of integers in the interval $[x^2,(x+1)^2]$ so that their product is in the form of ...
0
votes
2answers
81 views

For which values of $m$ $x^3\equiv 100 \pmod m$ is solvable?

While trying to get around this question, which is the positive integers solutions to $x^3=y^5+100$, I did some simple manipulations to get: $$q|y\implies x^3\equiv100\pmod q\\ p|x \implies ...
1
vote
4answers
99 views

Prove $5\mid2^{4n}-1$ by induction

For all $n\ge1$, use mathematical induction to establish each other the following divisibility statements: $$5\mid2^{4n}-1$$ I was wondering if someone could help me with the set up of this ...
-2
votes
2answers
185 views

Prove or disprove: If $a\mid (b+c)$, then either $a\mid b$ or $a\mid c$

Prove or disprove: If $a\mid (b+c)$, then either $a\mid b$ or $a\mid c$ I'm so confused how to go about this since it says prove or disprove. Should I start off by doing proof by contradiction? Step ...
2
votes
3answers
104 views

Does $b^2 = 4a + 2$ have integer solutions?

I got the following question on an exam I had today: $$b^2 = 4a+2$$ I said that it didn't since $b^2 -2$ was not a multiple of $4a$ or in other words, was not divisible by $4$. Is this correct?
0
votes
2answers
52 views

Congruences help

Theorem: Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m) and ac ≡ bd (mod m). Proof:We use a direct proof. Because a ≡ b (mod m) and c ≡ d (mod m), by ...
8
votes
2answers
259 views

At least one prime between $\sqrt{n}$ and $n$?

Prove that for all $n>2$ there exists at least one prime $p$ such that $\sqrt{n}<p<n$ using elementary methods. My try: If not, $\sum_{p<\sqrt{n}} (\lfloor n/p \rfloor-\lfloor \sqrt{n}/p ...
2
votes
2answers
75 views

Prove that $r_1 = r_2$ iff $n | (b - a)$

I need to know if I'm clear in my proof since I will have to present the answer to my class. Here's the full question: Let $n$ be a fixed positive integer. Then for any integers $a$ and $b$, let ...
0
votes
1answer
69 views

The least value of $a + b + c$ where $a,b,c$ are not perfect squares but their pairwise products are

The positive integers $a$, $b$ and $c$ are all different. None of them is a square but all the products $ab$, $ac$ and $bc$ are squares. What is the least value that $a + b + c$ can take? A $14$ B ...
1
vote
3answers
63 views

zeroes to polynomials in residue rings of Z

I'm supposed to find zeroes of $x^{12} -16$ in $\mathbb Z_{17}$, seems simple enough but I just can't seem to make any progress. I realize of course that we have $X^{12} = -1$ in $\mathbb Z_{17}$, ...
2
votes
1answer
83 views

What is the distribution of destiny numbers

Today my wife surprised me with the fact, that our destiny numbers (see e.g. http://numerologylife.com/destiny_number) are the same, namely we both have a destiny number of two. But I suspect that ...
8
votes
5answers
195 views

Pseudo-pythagorean theorem

Pythagoras' theorem is a special case of the Cosine theorem for a angle of $90°$. But also for an angle of 60° and 120°, "aesthetical" special cases derive: $c^2=a^2+b^2\pm ab$ First question: Are ...
4
votes
0answers
242 views

Let $n$ be a positive integer. If $2+2\sqrt{28n^2+1}$ is an integer, then it is a perfect square.

Let $n$ be a positive integer. If $2+2\sqrt{28n^2+1}$ is an integer, then it is a perfect square. My work: $2+2\sqrt{28n^2+1}=m \implies 4(28n^2+1)=m^2-4m+4 \implies m=2k$ $28n^2+1=k^2-2k+1 ...
4
votes
1answer
330 views

A 5x5 board has 25 cells.The numbers $\{1,2,3,4,5\}$ are written on every row,every column and the two main diagonals.

A 5x5 board has $25$ cells. The numbers $\{1,2,3,4,5\}$ are written on every row,every column and the two main diagonals without any repetition. If the sum of the numbers of the diagonal below the ...
1
vote
1answer
50 views

$p \equiv 5 \mod8\Rightarrow p=(2x+y)^{2}+4y^{2}$

If $p \equiv 5 \mod8$ , then $p=(2x+y)^{2}+4y^{2}$,for some x and y integers. Thanks Here is my approach: I know $p \equiv 5 \mod8\Rightarrow $ $p \equiv 1 \mod4\Rightarrow $ $n^{2}+m^{2}=p\equiv ...
1
vote
0answers
27 views

How man base $b$ automorphs are there with n or fewer base $b$ digits if $b$ has prime-power factorization

Definition: An integer $x \geq 2$ is called an automorph to the base $b$ if the last $n$ base $b$ digits of $x^2$ are the same as those of $x$ Question: How man base $b$ automorphs are there ...
0
votes
2answers
164 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
2answers
167 views

How to symplify a linear congruence?

How do we simplyfy a linear congruence such as 30u + 26 ≡ 3 (mod 7) to such u ≡ 6 (mod 7) . ?
0
votes
3answers
84 views

Why does $n^2 \equiv 10 \pmod{30}$ imply $n \equiv 0 \pmod{10}$?

It seems that $n^2 \equiv 10 \pmod{30} \iff n \equiv 0 \pmod{10}$. I found this by calculating $\{n \in \mathbb N_0 \mid n < 30 \land n^2 \equiv 10 \pmod{30}\} = \{10, 20\}$, and noting that 10 ...
4
votes
3answers
238 views

Product of $n$ consecutive positive integer is not a $n$th power?

If $n>2$ and $k$ is positive integer, then there is no positive integer $m$ satisfy that $$k(k+1)\cdots (k+n-1)=m^n\, ?$$ I tried to prove this problem, but I don't know how to prove it. I know ...
4
votes
2answers
120 views

Is it possible to solve $i^2+i+1\equiv 0\pmod{2^p-1}$ in general?

While looking at the Mersenne numbers (for prime $p$, the number $2^p-1$), I noticed that only certain of them had any solution to the modular equation $i^2+i+1\equiv 0\pmod{2^p-1}$, e.g., ...
2
votes
2answers
76 views

If $x\in\mathbb R$, solve $x^{\lfloor x\rfloor}=\frac{9}{2}$, where $\lfloor x\rfloor$ is the integer part of $x$.

If $x\in\mathbb R$, solve $x^{\lfloor x\rfloor}=\frac{9}{2}$, where $\lfloor x\rfloor$ is the integer part of $x$. Of course, $x=\lfloor x\rfloor+\{x\}$, where $\{x\}$ is the fractional part of ...
5
votes
3answers
321 views

Why would some elementary number theory notes exclude 0|0?

I am studying elementary number theory, and just started learning about divisors. I always, try to read several other sources mostly because it helps me understand ideas better, also the textbook I ...
1
vote
2answers
188 views

Find the LCM of 3 numbers given HCF of each 2.

Answer is I was totally confused when I saw the question. I never encountered a question like this. Can anyone tell me the way to solve this. I tried every method I could find but hard luck.
1
vote
2answers
50 views

A formula for a sequence which has three odds and then three evens, alternately

We know that triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36... where we have alternate two odd and two even numbers. This sequence has a simple formula $a_n=n(n+1)/2$. What would be an example ...
0
votes
2answers
85 views

Finding all integers a such that $a^3+a+1\equiv0 \pmod 5$

Just by eyeballing it and testing several values, I sense that the form $a^3+a+1$ is one such that it is never $\equiv0 \pmod 5$ as I can find no unique solution to start with and it seems to follow ...
5
votes
3answers
117 views

Are there any interesting examples of subsets of $\mathbf{N}$ that are known to be nonempty, but of which no elements are known?

There are many results in mathematics that establish the existence of some object without actually constructing said object. I am wondering if there are any interesting properties of the natural ...
1
vote
1answer
71 views

Use Fermat's little theorem to prove that $x ^{13} \equiv x$ mod 70 for any $x$

Use Fermat's little theorem to prove that $x ^{13} \equiv x$ mod 70 for any $x$. Any idea is appreciated.
0
votes
3answers
131 views

Discrete Mathematics Proof Question

Prove or disprove that there are infinitely many $x, y, z \in \mathbb N$ such that $$\frac{1}{x^2} + \frac{1}{y^2} = \frac{1}{z^2}$$ Currently, I tried to substitute $x, y,$ and $z$ with $2n$ and $n$ ...
1
vote
0answers
101 views

Is there a formula for finding the number of divisors of $n$ without factorize it?

I know that the number of divisors of $n$, $d(n)$ is $$d(n) = \Pi_{i=1}^k (a_i+1)$$ where each $a_i$ is the exponent of each prime factor of $n$. My question is: can I calculate $d(n)$ without know ...
2
votes
2answers
148 views

Discrete mathematics proof relating to Fermat's Theorem

Assuming the Fermat Theorem, show that there is no natural number $x$, $y$, and $z$ and $n\geq3$ such that $$\frac{1}{x^n} + \frac{1}{y^n} = \frac{1}{z^n}. $$ So far I think proof by contradiction ...
3
votes
1answer
67 views

Determining quadratic residues quickly

Let's say that I'm looking for all quadratic residues of a number. THe example from my book is 31. So I can just evaluate $i^2\equiv{a}\pmod{31}$, for $i=1..15$. While not a terribly difficult ...
3
votes
1answer
165 views

Explanation for Terry T. post

I read here that : " If one inserts these inequalities into the Legendre sieve and optimises the parameter, one can improve the upper bound for the number of primes in $[N,2N]$ to $$O \left(\frac{N ...
0
votes
0answers
48 views

Optimal substructure with regard to making change.

Suppose we have a set of integers $\{a_1,a_2\dots,a_n\}$. with the property that any integer number is of the form $c_1a_1+c_2a_2\dots+ c_n a_n$ with all the $c's being non-negative integers. The ...
6
votes
6answers
2k views

Prove that a number is even, given the cube is even

If it is known that $x^3$ is even, can we say that $x$ is even? It seems to be the case because an odd*odd*odd=odd (if we are dealing with natural numbers). But is there a proof?
4
votes
2answers
295 views

For a positive integer $n$ both $5n+1$ and $7n+1$ are perfect squares. Show that $n$ is divisible by 24.

My try: $5n + 1 = k^2$ $7n +1 = \frac{7k^2-2}5$ Just don't know how to proceed after this. Please help.
0
votes
2answers
268 views

The number of ordered triples $(a, b, c)$ of positive integers which satisfy the simultaneous equations $ab + bc = 44$, $ac + bc = 33$

My try: Subtracting the eqns: $a(b-c) = 11$ $a=1,b-c=11$ OR $a=11,b-c=1$ Substituting these values back int the original eqn. does not give an integral answer. Thus number of ordered ...
0
votes
1answer
90 views

Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
0
votes
2answers
47 views

For each of the following values of ($a,b$), find the largest number that is not of the form $ax+by$ with $x\geq 0$ and $y \geq 0$.

For each of the following values of ($a,b$), find the largest number that is not of the form $ax+by$ with $x\geq 0$ and $y \geq 0$. $(i) (a,b) = (3,7)$ $(ii) (a,b) = (5,7)$ $(iii) (a,b) = (4,11)$ ...
3
votes
2answers
177 views

Number-Theoretic Coin Puzzle

There are three piles of coins. You are allowed to move coins from one pile to another, but only if the number of coins in the destination pile is doubled. For example, if the first pile has 6 coins ...