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

learn more… | top users | synonyms (1)

9
votes
2answers
148 views

Are there infinitely many rational pairs $(a,b)$ which satisfy given equation?

I saw on some facebook page this concrete example: $1.2^2+0.6^2=1.2+0.6$ The question that immediately arises is: Are there infinitely many pairs $(a,b)$ of rational numbers such that we have $...
1
vote
2answers
104 views

Proving even and odd pythagorean triples

What is the most simplistic way to prove that, in a Pythagorean triple $(a,b,c)$ where $a^2 + b^2 = c^2$. If $c$ is even then so are both $a$ and $b$. Is it necessary to use modular arithmetic or is ...
0
votes
2answers
59 views

How to find all square roots of a number mod a product of primes.

How do you find the square root of a number mod a product of primes? I know that algorithms exist for finding the square root of a number mod a prime, such as tonelli-shanks, but I also know there ...
3
votes
2answers
61 views

If $(a,b)=1$ and $n$ is a prime, prove that $(a^n+b^n)/(a+b)$ and $(a+b)$ have no common factor, unless $a+b$ is a multiple of $n$

I have no hints to get started. This is a really tough problem involving prime powers and it's the first time I have seen such question. I need some good hints to get started. Thanks! Please do not ...
7
votes
1answer
748 views

Prove that $7 \mid abc(a^3-b^3)(b^3-c^3)(c^3-a^3)$

Let $a,b,c$ be positive integer. Prove that $abc(a^3-b^3)(b^3-c^3)(c^3-a^3)$ is divisible by $7$.
2
votes
0answers
58 views

Yet another question on finite fields

Let $p$ be prime, and let $m,n \in \mathbb{Z}$ be such that $m \mid pn$ but $m \nmid n$. Let $N^{pn}_n$ denote the norm function mapping $\mathbb{F}_{q^{pn}} \rightarrow \mathbb{F}_{q^n}$, defined by ...
3
votes
3answers
40 views

Every nonempty subset of the natural numbers has a least number

Proposition: Every nonempty subset $A$ of $\mathbb{N}$ has a least element. We assume the opposite: $$\exists \left( A \subseteq \mathbb{N} \wedge A \neq \varnothing \right): \forall s \in A: \...
1
vote
1answer
36 views

Is there a way to find sum of numbers to a certain power?

Suppose I have 4 numbers, for example (0, 2, 3, 5) and I square them ie (0, 4, 9, 25) and then sum them (38). Is there a formula for determining what the sum would be if these numbers were raised to ...
0
votes
1answer
231 views

Large sum of 1/GCD's

The problem is related to cryptography, it involves finding the sum of inverse of $GCD$... Say I have an integer $N \leq10^7$, Find sum of all $N/GCD(K,N)...$upto $N$ where $1\leq K\leq N$ Please ...
0
votes
5answers
70 views

Prove by induction that for all $n \in \mathbb{N} $, $(1+\frac {1} {2})^n\geq 1+ \frac{n} {2}$

I have been messing around with this one for a while, I thought of using a binomial expansion like $(1+\dfrac {1} {2})^{(n+1)} = (1+ \dfrac {1} {2})^n(1+ \dfrac {1} {2})=(1+\dfrac {1} {2})\sum _{i=0}^...
0
votes
1answer
41 views

Show that if $\gcd(m,n)$ divides $c-d$ then $\exists z \in\mathbb Z$ satisfying the pair of congruences (below).

Let $m,n \in\mathbb Z^+$ and $c,d \in\mathbb Z$. Prove that there exists $z\in\mathbb Z$ satisfying the pair of congruences: \begin{eqnarray} 
z \equiv c \bmod m \\ z \equiv d \bmod n 
 \end{eqnarray}...
2
votes
1answer
69 views

Prove the identity $\Sigma_{d|n}\phi(d) = n$, where the sum is extended over all the divisors $d$ of $n$.

let $\phi$ denote the Euler's function. Prove the identity $\Sigma_{d|n}\phi(d) = n$, where the sum is extended over all the divisors $d$ of $n$. attempt: Suppose $Z$ is a cyclic group of order $n$. ...
2
votes
1answer
38 views

Prove that $ a $ divides $1^{a^{n}} + 2^{a^{n}} + … + (a-1)^{a^{n}}$?

Let $a > 2$ be an odd number and let $ n $ be a positive integer. Prove that $ a $ divides $1^{a^{n}} + 2^{a^{n}} + ... + (a-1)^{a^{n}}$ ? (ref. Titu Andreescu, Number theory, page no. 5). I am ...
2
votes
1answer
58 views

Let $X=\{x|x=1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}, n\in \mathbb{N}\}$. Find $X \cap \mathbb{N}$ [duplicate]

I am out of hints here. Its trivial to show $1$ is a solution. How to show it's the only solution? Can someone please give me some hints? Please do not use congruence, limits or derivatives because ...
3
votes
2answers
20 views

If $(k,l) = 1$, show that $(b_2k-b_1l, a_1l-a_2k) = 1$ for $a_1b_2-a_2b_1=1$

Problem: If $(k,l) = 1$, show that $(b_2k-b_1l, a_1l-a_2k) = 1$ for $a_1b_2-a_2b_1=1$ Note: ($a_1, a_2,b_1,b_2,k,l \in \mathbb{Z}$) Also note that the actual (bigger) problem is: If $m = ...
2
votes
1answer
75 views

Chinese Remainder Theorem Modular

I have this problem, I need to find the smallest possible solution $$x \equiv 3 \pmod{10}, \\ x \equiv 11 \pmod{13}, \\ x \equiv 15 \pmod{17}.$$ I used Chinese remainder theorem and found that: $...
2
votes
0answers
31 views

Proving $n$ is psudoprime [closed]

Let $n = xy$ where $x$ and $y$ are distinct odd primes and let $g = \gcd(x - 1, y - 1)$ a) Prove that $n$ is a pseudoprime to the base $b$ if and only if $b^g = 1 \pmod n$ b) Conclude using part a) ...
5
votes
3answers
151 views

Fermat's infinite descent for finding the squares that sum to a prime

Fermat's theorem on sum of two squares states that an odd prime $p = x^2 + y^2 \iff p \equiv 1 \pmod 4$ Applying the descent procedure I can get to $a^2 + b^2 = pc$ where $c \in \mathbb{Z} \gt 1$ I ...
0
votes
1answer
28 views

Encrypting plaintext with RSA encryption scheme

I have an RSA encryption scheme with parameters $p$ = 31 $q$ = 37 $e$ = 17 I've decrypted the ciphertext $y$ = 2, using CRT and got the following plaintext: $8440 = 721 \pmod{1147}$ Now I ...
1
vote
1answer
43 views

Estimating the number of composite numbers less than a given $x$ that are relatively prime $6$

In a previous post, it was explained that the number of integers relatively prime to $6$ that are below a given $x$ is roughly $\frac{x}{3}$. I am wondering if it is possible use this result to ...
0
votes
1answer
55 views

Computing the inverse a^-1 mod n using Euler or Fermats Theorem

I'm trying to compute the inverse $a^{-1} \mod n$ with Fermat's Theorem (if applicable) or Euler's Theorem: $a$ = 6, $n$ = 13 I know that since n is prime, we can use Fermat's Theorem to compute the ...
5
votes
0answers
116 views

When $\frac{1}{n}\binom{n}{r}$ is an integer , again?

This question follows a previous one If $n$ and $r$ are coprime then $a_{n,r}=\frac{1}{n}\binom{n}{r}$ is integer but this is not a necessary condition. Question: what is a necessary and ...
1
vote
1answer
31 views

how to show that $\frac{\gcd(a,m)\gcd(b,m)}{\gcd(ab,m)} \in \mathbb Z$

I know this has been hinted at a previous page but I can't seem to find a complete answer. we know that $\gcd(a,m) = ax_1+mx_2$ from the euclidean algorithm. In a similar way, we know that $\gcd(b,m)=...
0
votes
0answers
19 views

Prove that $(a+b)^p$ = $a^p+b^p \bmod p$ for any prime $p$ [duplicate]

Prove that $(a+b)^p$ = $a^p+b^p \bmod p$ for any prime $p$ (and integers $a,b$) The given hint is use part A and the binomial theorem: I have proven part A, which is $ 0 < i < p$ then $p$ ...
4
votes
1answer
53 views

Prove that $N = \frac{(d_1 + d_2 + … + d_n)}{\frac{1}{d_1} + \frac{1}{d_2} + … + \frac{1}{d_n })}$?

How to prove that $$N = \frac{d_1 + d_2 + ... + d_n}{\frac{1}{d_1} + \frac{1}{d_2} + ... + \frac{1}{d_n }}$$ where $N \in \mathbb{N}$ and $d_1, d_2, ..., d_n$ are divisors of $N$?
4
votes
1answer
52 views

How do I prove this property of the sequence?

Given a sequence defined by the recursive formula: $$x_{1}=1 $$ $$x_{k+1}=x_{k}+(x_{k} \bmod 10)$$ Prove that : $$\forall n \in \mathbb{N}, n>0 \; \exists k (x_{k}=4^{n})$$ All I have tried is ...
2
votes
3answers
66 views

Find the least $n$ such that the expression is divisible by $700$.

What is the sum of the digits of the smallest positive integer $n^4 + 6n^3 + 11n + 6$ is divisible by $700$. Hints please. I got that $P(n) = n(n+1)(n+2)(n+3) \equiv 0 \pmod{700}$ I cannot seem ...
5
votes
0answers
58 views

Divisibility of $\binom{n}{r}$ by $n$. [duplicate]

This question is related to this other question (asked by user @GeraltofRivia). In fact it is what I understood the question to be before it was edited. Let $n\in\mathbb{N}$. For what $1\le r\le n-...
0
votes
1answer
47 views

Prove that if $a \in (\mathbb{Z/nZ})^\times$, then $-a \in (\mathbb{Z/nZ})^\times$?

Let $a \in (\mathbb{Z/nZ})^\times$ then $ax+ny = 1$ for some $x,y\in \mathbb{Z}$ $$-a = n - a$$ Then $$ny = 1 - ax = 1 + (-a)x$$ Putting value of -a $$ny = 1 + (n-a)x \qquad \implies (a-n)x + ny ...
3
votes
2answers
115 views

when is $\frac{1}{n}\binom{n}{r}$ an integer

So I am considering for which values of n is $a_n =\frac{1}{n}\binom{n}{r}$ an integer for all $ 1\leq r \leq n-1 $. The first thing I did was to check the Pascal Triangle. So I guess n has to be ...
2
votes
1answer
55 views

Prove that $(a+b, a-b) \ge (a, b)$

Note: $(x,y) := \gcd(x, y)$ Problem: Prove that $$(a+b, a-b) \ge (a,b)$$ for $a,b \in \mathbb{Z}$ Method: I used this method which failed. $$(a+b, a-b) = \min \{(a+b)x+(a - b)y | x,y \in \...
3
votes
0answers
43 views

Sum of residues modulo $m$

Let $c_1,c_2,\ldots,c_{\varphi(m)}$ be the reduced residue set modulo $m>2$. Show that $$c_1+c_2+\cdots+c_{\varphi(m)} \equiv 0 \pmod{m}.$$ My solution looks something like this. If $c_i \in {\...
2
votes
2answers
89 views

If $n$ is a square, can $n$ consist of only odd digits?

The question is: If $n$ is a square, can $n$ consist of only odd digits? I have a feeling that the answer is no, with the only exceptions being $n=1,9$. I am not sure how to go about proving this ...
7
votes
2answers
128 views

least common multiple of $\{1,2,…,n\}$ is bigger than $2^{n-1}$

The least common multiple of $\{1,2,...,n\}$ is greater than $2^{n-1}$ for any $n \ge 3$. I found this in a MATHEMATICA book, but I don't know how to prove this. Can you help me?
0
votes
1answer
81 views

Sum of the digits of two consecutive integers divisible by 17?

Find the smallest positive integer $n$ such that the digit sums of $n$ and $n + 1$ are both divisible by $17$ or prove that no such solution exists. My question was inspired when I couldn't find the ...
2
votes
2answers
53 views

How to solve this modular equation?

Find the smallest possible $n$ such that $n \equiv 1 \mod 5$ and $n \equiv 3 \mod 7$. The only method that I can think of to solve this is write out the two sequences defined by the $k$th terms $5k+1$...
2
votes
1answer
70 views

Estimating the number of integers relatively prime to $6$ between $1$ and some integer $x$?

I am trying to understand the standard way to estimate the number of integers relatively prime to $6$ where we don't know which congruence class $x$ belongs to. For a given $x$, if we know the ...
0
votes
1answer
67 views

Solution to congruence $z^2=c$ mod n

Could someone help me out with this? Not sure if I know all the tools to solve it. Let n be an int that is square free and odd with gcd(n,c)=1. Show that there is a z with $z^2=c$ mod n iff (c/p)=1 ...
1
vote
0answers
37 views

If $\gcd(Z,\sigma(Z))=1$ and $1<N=Z\sigma(Z)$, is $N$ always friendly?

This question is a generalization / offshoot of this earlier MSE post: If $\gcd(Z,\sigma(Z))=1$ and $1<N=Z\sigma(Z)$, is $N$ always friendly? Here, $\gcd(a,b)$ is the greatest common divisor ...
0
votes
3answers
50 views

Show that $51| 10^{32n+9} - 7$

Show that $51| 10^{32n+9} - 7$, use the Euler theorem to confirm that. Euler theorem states : $a^{\phi n} \cong 1$ mod $n$. $10^{32n+9} - 7 \cong 0$ mod $51$ $10^{32n+9} \cong 7 = 10^{32n} 10^9 = ...
2
votes
0answers
39 views

Understanding a proof : infinite prime numbers $p\equiv 1 \pmod4.$

Today, in exam, a purpose a an exercise was to prove that there exist an infinite prime numbers $p\equiv 1 \pmod4.$ First question it was to prove that $f:(\Bbb{Z}/p\Bbb{Z})^*\to(\Bbb{Z}/p\Bbb{Z})^*\...
2
votes
1answer
28 views

Prove that Diophantine equation $x^2=y^5+7$ doesn't have a solution

How to form one congruence relation on this equation? The starting congruence relation is $x^2\equiv y^5+7 \pmod {11}$ This seems wrong (for $x=2,y=3$). Could someone give a hint how to prove this?
1
vote
0answers
83 views

Why is proving that $10$ is solitary considered very difficult?

The title says it all. We denote the sum of the divisors of $x$ by $\sigma(x)$. The ratio $I(x)=\sigma(x)/x$ is called the abundancy index of $x$. If $I(m)=I(n)$, then $\{m,n\}$ is called a ...
1
vote
0answers
48 views

Is $p(p + 1)$ always a friendly number for $p$ a prime number?

Let $\sigma(x)$ denote the sum of the divisors of $x$. We call the ratio $I(x) = \sigma(x)/x$ as the abundancy index of $x$. A positive integer $N$ is friendly if there exists a positive integer $M \...
0
votes
1answer
43 views

What is the order of $10$ in $\mathbb{Z}_{17}$?

I'm getting confused between additive and multiplicative order. As I studied that "The order of an element of a group must divide the order of the group." Then what is the order of $10$? Is it $16$?
0
votes
3answers
88 views

Is $1010908899$ divisible by $7$ , $11$ and $13$?

So the given number is $1010908899$ and I showed that it is divisible by $11$ since $9-9+8-8+0-9+0-1+0-1=-11$ which is divisible by $11$ hence the number also. But how to check if it is also divisible ...
0
votes
1answer
40 views

If $\sigma(N) = aN + b$, where $\gcd(a, b) = 1$, does it follow that at least one of $N$'s factors is solitary?

Let $\sigma(x)$ be the sum of the divisors of $x$. If $\sigma(N) = aN + b$, where $\gcd(a, b) = 1$, $a \geq 2$, and $b$ could be negative, does it follow that at least one of $N$'s factors is ...
0
votes
0answers
31 views

Can distinct odd perfect numbers $N = {p^k}{m^2}$ share the same Euler factor $p^k$?

(A similar question has been asked in MO.) Let $\sigma(x)$ denote the sum of the divisors of $x$, and call the ratio $I(x) = \sigma(x)/x$ as the abundancy index of $x$. A number $N$ is called ...
1
vote
2answers
22 views

cubic residues mod pq, pq distinct primes

I have shown that the number of cubic residues mod $pq$ (including zero) is $(\frac{p-1}{3}+1)(\frac{q-1}{3}+1)$ where $p \equiv q \equiv 1$ (mod 3), using the Chinese Remainder Theorem. But how can I ...
0
votes
1answer
32 views

maximal element of a relation

Let $X = \mathbb{N}$. We define a relation $\preceq$ on X by: $x \preceq y$ if and only if there is $z ∈ X$ with $xz = y$. I am trying to find the maximal element(s) in this relation. Currently, I ...