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

learn more… | top users | synonyms (1)

1
vote
2answers
36 views

Property of additive group [closed]

Let $m \in \mathbb{Z}_q$, for a prime $q$ and $x \in \mathbb{A}$, where $\mathbb{A}$ is an additive group of order $q$. Then is it always true that $mx \in \mathbb{A}$? If true, how to prove it? ...
1
vote
2answers
65 views

Prove that there are infinitely many composite numbers of the form $2^{2^n}+3$.

There are infinitely many composite numbers of the form $2^{2^n}+3$. [Hint: Use the fact that $2^{2n}=3k+1$ for some $k$ to establish that $7\mid2^{2^{2n+1}}+3$.] If $p$ is a prime divisor of ...
1
vote
1answer
45 views

A proof that every set of natural numbers contains a minimal element

I'm currently trying to extend my basic knowledge and in order to do so, I started with the Peano-axioms. I think, I understand the underlying thoughts and I want to prove the following theorem using ...
3
votes
2answers
75 views

How to prove ${{pm} \choose {pn}}\equiv{m \choose n} \pmod{p}$.

Question:(1) if p is a prime and m,n $\in$ N,prove that ${{pm} \choose {pn}}\equiv{m \choose n} \pmod p$ (the book gives me a hint: think about $(1+x)^{pm}$ and $(1+x^m)^p$ in $F_{p}(x)$. (2) Prove ...
0
votes
1answer
37 views

using kronecker's theorem can we prove there's some power of two yielding a number whose initial digits equal my social security number?

I just watched the "Great Courses" series of lectures in number theory, in which Professor Burger stated that using Kronecker's theorem for any irrational number r, the sequence ({n * r}) ...
3
votes
3answers
71 views

The number of positive integral solutions to the system of equations.

The number of positive integral solutions to the system of equations $$\begin{align} & a_{1}+a_{2}+a_{3}+a_{4}+a_{5}=47\\ &a_{1}+a_{2}=37,\ \ \{a_{1},a_{2},a_{3},a_{4},a_{5}\} \in ...
1
vote
0answers
19 views

ElGamal signature for finding the private key

Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$.To ...
1
vote
1answer
36 views

An elementary number theory

Let n be a positive integer. Now we can write $(2^n)!= 2^{(xn+t)}.k$, where $x,t$ and $k$ are positive integer such that $2$ does not divide $k$. How do we determine $x$ and $t$ based on $n$? Please ...
3
votes
1answer
46 views

Show that there are no integers that solve equation

I want to show that there are no integers $x, y$ that solve the following equation: $$ 15x-9y=100 $$ My solution would be: $$ 3\cdot5\cdot x-3\cdot3\cdot y = 100 \\ 3\cdot(5x-3y) = 100 \\ 5x-3y = ...
0
votes
1answer
26 views

Closeness of a number to mean.

Let's say I am given mean $\mu$ and deviation $\sigma$ of a set of numbers. I am now given $x$, a real number. Depending on how close $x$ is to $\mu$, I need a measure starting from 100 going down ...
2
votes
2answers
34 views

How to find the sum of the three digits of a number $N$ that gives the same remainder when $2272$ and $875$ are divided by it

On dividing $2272$ as well as $875$ by three digit number $N$, we get same remainder. What is the sum of the digits of $N$? I cannot start hit and trial method here, so how should I do this? ...
0
votes
3answers
45 views

What is the unit digit in $(3547)^{153} \cdot (251)^{72}$ [closed]

What is the unit digit in $(3547)^{153} \cdot (251)^{72}$ . How can i do it with methods taught in school ? Thanks
0
votes
4answers
44 views

Prove or disprove $\max\{a,\max\{b,c\}\}=\max\{\max\{a,b\},c\}$

For and $a,b,c\in \Bbb Z, $ how can I prove or disprove 1. $\max\{a,\max\{b,c\}\}=\max\{\max\{a,b\},c\}$ and 2. $\min\{a,\min\{b,c\}\}=\min\{\min\{a,b\},c\}$ We know that, ...
2
votes
1answer
28 views

Smallest integer

I encountered an intriguing problem and I think I have a solution, but I want to run it by some of the smarter people around here: Find the smallest integer $n, n>1$ such that $C(n)=n, C(n)$ is ...
1
vote
0answers
28 views

Is this :$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $ irrational series for every natural number $k$?

Is this: $$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $$ irrational series for every natural number $k$? Where : $\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of ...
3
votes
1answer
50 views

Largest sum of compatible triples

A triple $(a,b,c)$ of distinct integers is called compatible if at least one of them, say $b$ has the property that either $n\mid b$ or $b\mid n,$ for each $n\in\{a,c\}.$ Let $X$ be the set of all ...
3
votes
3answers
65 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
80 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
51 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
50 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
15 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
67 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
57 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
27 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
104 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
44 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
44 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
37 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 ?