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

learn more… | top users | synonyms (1)

3
votes
3answers
66 views

For any integer $n>1$ exist integers $a$ and $b$ so that $\tau(a)+\tau(b)=n$

How to prove that for any integer $n>1$ exist integers $a$ and $b$ so that $$\tau(a)+\tau(b)=n$$ Remark: $\tau(n)$ is the number of positive divisors of $n$.
2
votes
4answers
82 views

Prove that $(a,b)^2=(a^2,b^2,ab)$

I am trying to prove that $(a,b)^2=(a^2,b^2,ab)$ and was told that this follows from some very basic $\gcd$ laws. What am I not seeing?
2
votes
2answers
52 views

Sailor,Monkey,Coconut answer in elaborate

In Sailor, Monkey, Coconut Problem Can anyone tell me how adding 56 gives me another solution??I understand that cocount is divided into 5 piles.But how is 56 give me another solution?why wouldn't ...
1
vote
2answers
64 views

How many such polynomial exist?

Find the number of second-degree polynomials $f(x)$ with integer coefficients and integer zeros for which $f(0)=2010$. I got: $$P(x) = ax^2 + bx + c \implies P(0) = c = 2010$$ Let $P(r_1, r_2) ...
0
votes
1answer
60 views

prove if $xyk \neq 0$, then: $x^3=3(k+xy)(k-xy-y^3)$ has no integral solutions.

Let $\gcd(x,y)=1, k \in \mathbb{Z}$ and $x \equiv 0 \pmod 3$. Show that if $xyk \neq 0$, then: $$x^3=3(k+xy)(k-xy-y^3)$$ has no integral solutions. Any hints? I keep getting lost in my reasoning.
1
vote
1answer
45 views

Probability of not making a shoe pair.

Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The ...
3
votes
2answers
83 views

Given that $p$ is an odd prime, is the GCD of any two numbers of the form $2^p + 1$ always equal to $3$?

I have checked it for some numbers and it appears to be true. Also I am able to reduce it and get the value $3$ for specific primes $p_1$, $p_2$ by using the Euclidean algorithm but I am not able to ...
3
votes
1answer
65 views

Why doesnt this Combinatoric work two ways?

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements ...
1
vote
1answer
54 views

If the Chaos Game result is a Sierpinski attractor when the random seed is a sequence (Möbius function), does it imply that the sequence is random?

The Chaos Game is the famous method to create fractals elaborated by professor Michael Barnsley. As Wikipedia explains: "The fractal is created by iteratively creating a sequence of points, starting ...
1
vote
1answer
30 views

$\forall A\subset \mathbb{N}$ the sum of the reciprocals of $A$ diverges iff $A$ is $(\tau, \mathbb{N})$-dense

Show that is possible to endow the natural numbers with a topology $\tau$ such that for every $A\subset \mathbb{N}$ the sum of the reciprocals of $A$ diverges iff $A$ is $(\tau, \mathbb{N})$-dense.
2
votes
1answer
16 views

Multiply numbers that are modulo $M$

Let's say $a$ modulo $M$ is $r_j$. How I can prove that $sa$ modulo $M$ is still $r_j$ and not another integer, where $\gcd(s,M)=1$.
3
votes
4answers
50 views

How do I show that we can't write $N=114^n-1$ as sum of $3$ squares for all natural number $n>2$?

I run some computations in wolfram alpha, I see that we can't write :$$N=114^n-1$$ as sum of $3$ squares, then Hop someone who can show me how I do prove that we can't write $N=114^n-1$ as sum of $3$ ...
1
vote
3answers
58 views

How many possible guesses?

A game show offers a contestant three prizes A, B and C, each of which is worth a whole number of dollars from $ 1$ to $ 9999$ inclusive. The contestant wins the prizes by correctly guessing the ...
0
votes
3answers
71 views

Is this : $\lim \sup\frac{\sigma(n)}{n} , n \to\infty $ has a finite limit?

The asymptotic growth rate of the sigma function can be expressed by : $$\lim \sup\frac{\sigma(n)}{n\log(\log(n))}=e^{\gamma}$$ $$n \to\infty$$ according to the above limit , Is this : $$\lim ...
8
votes
3answers
108 views

Prove that $(\sqrt2 − 1)^n, \forall n \in \mathbb{Z^+}$ can be represented as $\sqrt{m} − \sqrt{m−1}$ for some $m \in \mathbb{Z^+}$ (no induction).

From the 1994 Canada National Olympiad: Prove that $(\sqrt2 − 1)^n, \forall n \in \mathbb{Z^+}$ can be represented as $\sqrt{m} − \sqrt{m−1}$ for some $m \in \mathbb{Z^+}$. I think one ...
5
votes
1answer
72 views

How many ways are there to shake hands?

In a group of $9$ people, each person shakes hands with exactly $2$ of the other people from the group. Let $X$ be the number of possible ways to perform these handshakes. Take $2$ handshake ...
2
votes
1answer
59 views

ABC conjecture consequence

At page 6 of the book: "Prime Numbers The most mysterious figures in Math" this statement is listed as one of the consequences of the ABC conjecture: There are Infinitely many Wieferich primes. This ...
0
votes
2answers
75 views

prove number is an integer [closed]

So I have the following statement: $a$ is a positive integer and $x = \sqrt[n]{a}$ that has the charesteristic $x^n=a$. Show that $x$ is a rational number. I know that a rational number is on ...
0
votes
0answers
28 views

Exponential cryptosystem

The cryptosystem works as follows: The plaintext message is first replaced by ciphers (a=00, b=01, etc.) and then encrypted in blocks of four digits. So if the message is "hi", the plaintext number ...
0
votes
4answers
35 views

How can I calculate these large exponents with mods?

Is there a fast technique that I can use that is similar in each case to calculate the following: $$(1100)^{1357} \mod{2623} = 1519$$ $$(1819)^{1357} \mod{2623} = 2124$$ $$(0200)^{1357} \mod{2623} ...
3
votes
4answers
109 views

Find the smallest positive integer that ends in $17$, is divisible by $17$, and the sum of its digits is equal to $17$.

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with primes and composities but other than that, the textbook gave no hints ...
3
votes
1answer
45 views

Finding period of a recursive sequence defined by modular operator?

If $f(x)$ is defined as : $f(x)=i$ ,if $x\equiv i$ (mod n), $0\leq i< n$ How can I prove whether the following recursive sequences are periodic or not? ...
1
vote
2answers
46 views

Largest Arithmetic Sum of Relatively Prime Numbers Under 30

Pick however many integers in the range $[1,30]$ (inclusive). The only constraint is that all of these numbers must be relatively prime to each other. What is the largest possible arithmetic sum ...
0
votes
0answers
45 views

Divisibility Question [duplicate]

If $(ab+1)$ divides $(a^2+b^2)$ then prove that $(a^2+b^2)$ when divided by $(ab+1)$ gives a square of an integer.
-5
votes
8answers
62 views

Find the smallest integer $n$ [closed]

Find the smallest integer $n$, such that $$n\left ( \sqrt{101}-10 \right )> 1$$
1
vote
0answers
41 views

Gauss' Lemma Proof Clarification

I am trying to follow a proof of Gauss' lemma in Number Theory by George Andrews. I have a few problems with a couple assumptions made. Let g.c.d.$(m,p)=1$ where $p$ is an odd prime, and let $\mu$ be ...
4
votes
0answers
203 views

Integer solutions of a cubic equation

With $\mathrm {gcd}(x,y)=1$ I have the following equation: $$x^3-xy^2+1=N$$ I want to find the integer solutions, given an N, of the variables $x$ and $y$. I have tried factoring the equation into ...
5
votes
1answer
48 views

Consider the 1000-element subsets

Consider all 1000-element subsets of the set $A = \{ 1, 2, 3, ... , 2015 \}$. From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q}$, ...
0
votes
1answer
28 views

Absolute value. Elementary number theory part of proof.

I have a very basic question taken from my a part of a proof in elementry number theory textbook. My textbook states: Given that $x\geq 0, y<0$ and $0\leq x+y$, this implies that $$\left| ...
5
votes
1answer
62 views

Infinite number of ways to write $1=\frac{1}{n}+\frac{1}{a_1}+\cdots+\frac{1}{a_k}$

How can I show that there is an infinite number of ways in which $1$ can be written in the form $$1=\frac{1}{n}+\frac{1}{a_1}+\cdots+\frac{1}{a_k},$$ where $n>1$ is an integer (this number is ...
3
votes
2answers
87 views

How to replace addition with multiplication to find the next integer value?

Sorry in advance for my lack of mathematical knowledge, I am very new to it. Yesterday, I posed this question to myself: "In a world without addition or subtraction, how could we derive the next ...
0
votes
0answers
19 views

Create a recursion here [duplicate]

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain either exactly two adjacent chairs or no adjacent chairs. I had this question before, but I ...
1
vote
1answer
38 views

Unfairish Probability

Charles has two six-sided dice. One of the dice is fair, and the other die is biased so that it comes up six with probability $\frac{2}{3}$ and each of the other five sides has probability ...
1
vote
2answers
63 views

Modulus and Fermat's Little Theorem

How do I calculate $ 11^{23} \bmod{163} $ using fermat's little theorem ?
2
votes
2answers
64 views

Number of solutions of $a^{3}+2^{a+1}=a^4$.

Find the number of solutions of the following equation $$a^{3}+2^{a+1}=a^4,\ \ 1\leq a\leq 99,\ \ a\in\mathbb{N}$$. I tried , $$a^{3}+2^{a+1}=a^4\\ 2^{a+1}=a^4-a^{3}\\ 2^{a+1}=a^{3}(a-1)\\ ...
6
votes
5answers
80 views

Show that $4$ does not divide $x^3-2$

Show that $4$ does not divide $x^3-2$ is what I need to prove. I think I should put $4k$ is $x^3-2$ and then contradict it somehow. Alternatively is to factor it out as $x^3$ is $x(x+2)(x-2)$ but I ...
2
votes
2answers
150 views

Group Theory: group under the composition multiplication modulo $p$

Suppose you have a group $G(S,*)$ where $S=\{1,2,\ldots,p-1\}$, $p$ is prime number, and $*$ is equivalent to the multiplication$\mod p$. If $a,b$ belong to $S$, then $ab\pmod{p}$ also belongs to ...
0
votes
0answers
67 views

Why doesn't combinatorics work here?

A while ago I asked one-to-one in combinatorics and then using one-to-one I'll repeat my answer here: There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are ...
-1
votes
1answer
41 views

Find all the answers to this equation [closed]

Let $n$ be a natural number. Find all the answers to the following equation. $(a,b)$ is the greatest common divisor of $a$ and $b$. $$( n! + n + 1 , n! + 2 ) = 1$$
2
votes
0answers
49 views

Beal Conjecture and ($\bmod 3$) operation [closed]

When we apply a ($\bmod 3$) operation on the $A^x +B^y =C^z$ we will see some strange results. For e.g.: Let $A=6m+1$ & $B=6n+1$. Since $A$ & $B$ are odd numbers, $C$ will have to be even. ...
0
votes
1answer
27 views

How do I show that :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number?

How do i show this if it's not an open problem :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number and p is prime number. and $\sigma({p^m})$ is sum divisors of $p^m$ ...
1
vote
1answer
41 views

When does :$\sigma(\sigma(2n))=\sigma(\sigma(n))$ and $\sigma(n)$ is sum divisors of the positive integer $n$?

Is there someone who can show me When does: $$\sigma(\sigma(2n))=\sigma(\sigma(n))$$ where : $\sigma(n)$ denote the sum divisors of the positive integer $n$ ? Note (1) : I accrossed this problem when ...
2
votes
0answers
52 views

Composition factoring into nonnegative integer polynomials

Consider the integer polynomials with nonnegative coefficients, such as: $$ 1 + 2x +2x^2 $$ $$ 3 + 3x^4 + 11x^{10}$$ $$ 13 + 7x + x^2 $$ I asm interested in knowing "what is a composition ...
3
votes
1answer
31 views

Pairs with sum and product formed by the same digits but arranged differently

Find all pairs of natural numbers that have the sum and product formed by the same digits but arranged differently. I can't find the method to begin to solve it. A first example is obviously (9,9)
5
votes
3answers
97 views

If $5x+7y=2011$ show that $285<x+y<403$

Let $x,y\in\mathbb{N}$ two natural numbers that satisfy the equality \begin{equation}5x+7y=2011\end{equation} Show that \begin{equation}285<x+y<403\end{equation} The only thing I obtained ...
1
vote
2answers
17 views

Application of invariant method

On the board is written the number $18$. Every minute the number is replaced by the product with 2 or 3,or by the quotient of the division with 2 or 3. Show that after $60$ minutes the number cannot ...
1
vote
1answer
61 views

Solve $n(n+1) \equiv 0 \pmod{1004}$

Solve: $$n(n+1) \equiv 0 \pmod{1004}$$ For the smallest possible $n > 0$. It's either $n \equiv 0$ or $n \equiv -1 \pmod{1004}$. The correct answer is $251$, I'm not sure how though.
5
votes
3answers
102 views

How many ways to arrange the flags?

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements ...
3
votes
1answer
43 views

One-to-One correspondence in Counting

I have a confusion on the one-to-one correspondence in combinatorics. Take the problem: In how many ways may five people be seated in a row of twenty chairs given that no two people may sit next ...
1
vote
2answers
35 views

Order of 10 in $\mathbb{Z}/p\mathbb{Z}$ equals order of 10 in $\mathbb{Z}/99\mathbb{Z}$ for p>11 prime

Why is the order of 10 in $(\mathbb{Z}/p\mathbb{Z})^\times$ equal to the order of 10 in $(\mathbb{Z}/99p\mathbb{Z})^\times$ for $p>11$ prime?