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

learn more… | top users | synonyms (1)

0
votes
3answers
40 views

remainder of $a^2+3a+4$ divided by 7

If the remainder of $a$ is divided by $7$ is $6$, find the remainder when $a^2+3a+4$ is divided by 7 (A)$2$ (B)$3$ (C)$4$ (D)$5$ (E)$6$ if $a = 6$, then $6^2 + 3(6) + 4 = 58$, and $a^2+3a+4 ...
0
votes
2answers
39 views

Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$.

I have been working through the following proof: Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$. Below, I have included screenshots of the ...
0
votes
3answers
36 views

Chinese remainder theorem for three equations?

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences? $$x \equiv a \bmod A$$ $$x \equiv b \bmod B$$ $$x \equiv c \bmod C$$ Assuming all values are ...
2
votes
1answer
50 views

How to show $n$ is a prime number?

Let $a$ and $n$ be integers greater than 1. Suppose that $a^n-1$ is a prime. Show that $a=2$ and $n$ is a prime. What can you say about primes of the form $2^n+1$? By ...
0
votes
0answers
49 views

Curious GCD Divisibility Relation

In some of my recent work, I have accidentally discovered in an extremely convoluted manner the following result: Suppose $a,b$ are positive integers less than some other positive integer $c$, and ...
0
votes
0answers
10 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
-7
votes
1answer
25 views

Find the number of 5 digit positive integers that are divisible by 11 [on hold]

Find the number of 5 digit positive integers that are divisible by 11. Options are $9191$ $8180$ $9190$ $8181$
0
votes
5answers
108 views

Why are sums of powers of 2 able to give all numbers?

It is known that If we sum up a combination of numbers that are positive powers of 2(starting from 0 to infinity), we can get any number possible. (Correct me if this is wrong). Can anyone ...
-1
votes
2answers
39 views

The sum of three natural numbers are $111$, and the three numbers are in geometric progression.

Find all triples of natural numbers $(a,b,c)$ such that $a,b$ and $c$ are in geometric progression, and $a+b+c=111$. Any pointers?
0
votes
1answer
23 views

Probability the range is disjoint

Let $A=\{1,2,3,4\}$, and $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A$. The probability that the range of $f$ and the range of $g$ are disjoint is ...
2
votes
1answer
26 views

Given $n>0$, let $S$ be a set whose elements are positive integers $\leq 2n$ such that:

S is a set with the property that for all a,b∈S with $a<b$, a doesn't divide b. What is the maximum number of integers that $S$ can contain ? I thought it was the number of prime numbers smaller ...
0
votes
3answers
62 views

Integer solutions to $\frac{1}{a} + \frac{1}{b} = \frac{1}{12}$.

$$\frac{1}{a} + \frac{1}{b} = \frac{1}{12}$$ I'm trying to find all integer solutions to this equation. I've played with this equation algebraically to see if I can figure out the restrictions on $a$ ...
-3
votes
2answers
49 views

All natural numbers $m, n$ such that $m = \sqrt{\frac{1}3A^2 - 3n^2}$ [on hold]

I have $m = \sqrt{\frac{1}3A^2 - 3n^2}$. A is a known integer. How do I find all solutions for what m and n are if both m and n are naturals (round positive numbers)
19
votes
1answer
245 views

Is $1992! - 1$ prime?

Consider the factorials, defined inductively by $1! = 0! = 1$ and $n! = n\cdot(n-1)!$ for $n \geq 2$. Question: Is $1992!-1$ a prime number? The question is from a book, maybe is contest math ...
3
votes
1answer
41 views

Proof of Cohn's Irreducibility Criterion

I was looking for an elementary (or involving introductory level abstract algebra/analysis) proof of Cohn's Irreduciblity Criterion: If $$ a_0, a_1, \dots, a_n \in \Bbb{Z} $$ and $$ 0 \le ...
2
votes
3answers
88 views

High computation in probability

Six men and some number of women stand in a line in random order. Let $p$ be the probability that a group of at least four men stand together in the line, given that every man stands next to at ...
1
vote
1answer
36 views

Euler's Phi function, elementary number theory

Show that the equation $\phi(n)=2p$ where $p$ is prime and $2p+1$ is composite has no solutions. Using formula for $\phi$ it's quite easy proving $n$ cannot have more than two prime factors in its ...
-1
votes
1answer
35 views

Is 1 coprime to itself? [on hold]

Is $\{1,1\}$ a pair of co-prime numbers? According to the definition, two numbers are coprime if $\gcd(a,b)=1$, and for $\{1,1\}$ it is true that $\gcd(1,1)=1$.
1
vote
0answers
45 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
2
votes
2answers
87 views

Sum of remainders of $2^n$

Hints Only Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$ be the sum of all elements in $R$. Find the ...
4
votes
2answers
40 views

Number of divisors of the form $(4n+1)$

Find the number of divisors of $$2^2\cdot3^3\cdot5^3\cdot7^5$$ which are of the form $(4n+1)$ I know how to find the total number of divisors. But, to find the number of divisors of the form ...
2
votes
0answers
21 views

$x-y^4= LCM(x, y)$ [duplicate]

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 the least common multiple, but other than that, the textbook gave no hints ...
-2
votes
1answer
45 views

Describe a fast (polynomial time)algorithm who takes as input the elements $g^a,g^b$ and gives as output the element $g^{a \cdot b}$

Let $q$ prime number, $G$ a cyclic group with order $q$ and $g \in G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$. ...
3
votes
3answers
54 views

Nonnegative Integer solutions of $x+y-xy=0$

I would like to see other methods, besides the one I use here to find all the nonnegative integer solutions of an equation like $$x+y-xy=0$$. This is the one I used: First we note that for $x=1$ ...
1
vote
0answers
14 views

Maximum bound of number of prime factors

This comes from the proof of theorem 4.2.1 from The Probabilistic Method by Alon and Spencer. Letting $\nu(n)$ be the number of primes $p$ dividing $n$, here's an excerpt verbatim: Let $x$ be ...
1
vote
2answers
22 views

Algorithm for finding prime numbers of specific form

Given the natural number $n$,who is in the form $p^2 \cdot q^2$,with $p$,$q$ prime numbers.Also $φ(n)$ is given.Describe a fast algorithm(polynomial time) that calculates the $p$ and $q$.Apply your ...
3
votes
3answers
69 views

Is it possible to find integer $n$, $m$ so $6n=7m+1$ without manual search?

I was dealing with a childish problem, which eventually led to this: Find integer $n$ and $m$ to fit the equation $6n=7m+1$ I immediately found first numbers by simple enumeration ($n=6$, ...
2
votes
3answers
58 views

Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$

Here is a very elementary number theory proof using strong induction. Please mark/grade. Prove that $$\sum_{d|n}\phi(d)=n$$where $\phi$ is the Euler's phi function, $n,d\in\mathbb{N}$ First, ...
2
votes
3answers
82 views

Explain the proof that the root of a prime number is an irrational number

Though the proof of this is done in a previous question i have a doubt in a certain concept so i ask to clear it.In the proof we say that $\sqrt{p} = \frac{a}{b}$. (In their lowest form.) $p = a^2 ...
0
votes
3answers
40 views

What does P|a means?

In the proof for the existence of unlimited prime numbers, i saw the following let n be the number of prime numbers as P1,P2,P3,.......Pn let a = P1P2P3....Pn+1 a > Pn and a is not a prime number a ...
0
votes
1answer
29 views

What does the symbol $N(\mathfrak{p}_{i})=P^{k_i}$ mean in theorem of Dedekind?

When I was reading an article about linear recurrence relations, I saw this notation: $$P=\mathfrak{p}_1^{e_1}\mathfrak{p}_2^{e_2}...\mathfrak{p}_r^{e_r}$$ $$ N(\mathfrak{p}_{i})=P^{k_i}$$ What is ...
2
votes
2answers
48 views

What is $k$ so that $\frac {1001\times 1002 \times … \times 2008} {11^k}$ will be an integer?

I found this question from last year's maths competition in my country. I've tried any possible way to find it, but it is just way too hard. What is the largest integer $k$ such that the following ...
1
vote
1answer
46 views

How to prove that ways of $n$ of the form $a+bd\ $ equals $\ \varphi(n)?\ $ Where $\ n,\ a,\ b,\ d\ \in \mathbb{Z}^+,\ n > 1,\ d \geq a,\ (a,d)=1$.

How to prove that ways of $n$ of the form $a+bd\ $ equals $\ \varphi(n)?\ $ Where $\ n,\ a,\ b,\ d\ \in \mathbb{Z}^+,\ n > 1,\ d \geq a,\ (a,d)=1,\ \varphi(n) \ $is Euler's totient function.
1
vote
0answers
35 views

On Catalan's complete solution to the equation $T^2=U^2+V^2+W^2$

Catalan proved the following: If $t,u,v,w$ are coprime integers such that \begin{equation*} t^2 = u^2 + v^2 + w^2, \end{equation*} then there exist integers $\alpha,\beta,\gamma,\delta$ such that ...
0
votes
3answers
51 views

How to solve this equation with ceiling function?

Given that $x$ is a positive integer, find $x$ in $(E)$. $$\tag{E} j-n=x-n\cdot\left\lceil\frac{x}{n}\right\rceil$$ All $n, j, x$ are positive integers.
0
votes
0answers
47 views

Applying the sum-of-digits operation to $4444^{4444}$ three times [duplicate]

$A$ is the sum of the digits of $4444^{4444}$. $B$ is the sum of the digits of $A$. Then what will be the sum of digits of $B$? I found this in the question paper of Mathematical Tripos Exam of ...
2
votes
2answers
66 views

How to solve “ways of seating around a circular table”

Recently I asked a question about seating, here it is again: The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five ...
0
votes
2answers
58 views

Velleman's exercise $3.1.7$

Prove that if $a^3>a$ then $a^5>a$. Velleman gives this "hint": $$\text{One approach is to start by completing the following equation:}\ (a^5-a)=(a^3-a) \cdot x$$ I don't understand this ...
-4
votes
1answer
56 views

Prove that there doesn't exist any integer $x \ge 3$ such that $x^2-1$ is prime. [on hold]

Prove that there doesn't exist integer $x \ge 3$ such that $x^2-1$ is prime.
1
vote
2answers
72 views

How many ways to arrange the seating?

The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with ...
1
vote
1answer
41 views

How many solutions for $(6b)^b\equiv (12b-k)^b\mod p$?

Rephrasing my previous question; If $(6b)^b\equiv (12b-k)^b\mod p$, where $b$ is odd and $p=1+6qb$, and where $p$ and $q$ are prime, are there any solutions for $k$ other than $k\equiv6b\mod p$?
2
votes
4answers
83 views

If $a^b\equiv c^b\mod p$, can we conclude that $a\equiv c\mod p$?

If $a^b\equiv c^b\mod p$, is is true that $a\equiv c\mod p$, where $b$ is odd and $p$ is prime? We know that if $a\equiv c\mod p$, then $a^b\equiv c^b\mod p$. Is the reverse true?
2
votes
5answers
81 views

Find all of the prime factors of $ 20! $

Could someone please give me a hint on how to go about this? I have pretty much missed one week of summer school so I don't know if there is a more elegant way to arrive at a solution other that using ...
3
votes
0answers
44 views

Are there any other integer points on the elliptic curve $Y^2 = X^3 + 1$ beyond $(-1, 0), (0, \pm 1), (2, \pm 3)$?

The charm of elliptic curves is that given one or two integer points, one can find others by the group law. However the easy to guess points from the title just pump me around trough a cyclic group of ...
3
votes
1answer
49 views

Positive Integers Equation

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 the least common multiple, but other than that, the textbook gave no hints ...
0
votes
1answer
46 views

What is the relative density of the abundant numbers in the positive integers?

The Art and Craft of Problem Solving by Paul Zeitz has the following problem. Now, I have been able to solve parts (a) and (b), part (a) by showing that it can get arbitrarily large, and part (b) by ...
0
votes
0answers
25 views

Questions about RSA cryptosystem primitives: key construction and signature

i) Construct a pair of private/public key RSA, where the prime numbers that you will use are $p=11$ and $q=13$ ii) Describe how the owner of the above keys calculates a signature RSA in the message ...
2
votes
0answers
23 views

Fast multiplication times a fixed constant $A$?

Is there a way to speed up integer multiplication of billions of $B_{i}$'s times a fixed $A$? We can configure $A$ to be either small compared to the $B_{i}$'s (e.g. $10^{10}$ compared to $10^{200}$) ...
1
vote
2answers
35 views

Property of additive group [on hold]

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 ...