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

learn more… | top users | synonyms (1)

6
votes
1answer
78 views

Show that among any consecutive $16$ natural numbers one is coprime to all others

Show that among any consecutive $16$ natural numbers one is coprime to all others. Is it useful to use the division algorithm on $16$? $16k,16k+1,16k+2,...16k+15$
3
votes
0answers
17 views

$R=\{ m+nr\sqrt{2} \mid m,n \in \Bbb Z \}$ and $I_{a,b}=\{ ma+n(b+r\sqrt{2}) \mid m,n \in \Bbb Z \}$

Let $r$ be a natural number and $R=\{ m+nr\sqrt{2} \mid m,n \in \Bbb Z \}$. We can show that $R$ is a subring of the ring $\Bbb Q [\sqrt{2}]$. My questions are as follows: $(1)$ Suppose that a ...
4
votes
2answers
72 views

Question from Mathcounts competition

The least positive integer that is divisible by $2, 3 ,4,$ and $5,$ and is also a perfect square, perfect cube, $4^{th}$ power, and $5^{th}$ power, can be written in the form $a^b$ for positive ...
0
votes
1answer
16 views

Worded linear congruence problem-Days/Years

The Melbourne cup is run every year on the first Tuesday in November. The US presidential elections are held every four years on the day after the first Monday in November. George W. Bush was elected ...
3
votes
2answers
47 views

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$.

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$. I want to know if my attempt is correct. First $a^{13} \equiv (a^3)^4 \cdot a \equiv a^4 \cdot a \equiv a^3 \cdot a^2 \equiv a \cdot a^2 ...
0
votes
2answers
54 views

Find an integer function $f(n)$ that is even for $n\not \equiv 2\bmod 3$, and odd for $n\equiv 2\bmod 3$

Does a function $f:\mathbb{N}\to\mathbb{N}$ that satisfies $$ f(n) \equiv \begin{cases}0 \bmod{2}, & n\equiv 0,1\bmod{3} \\ 1\bmod{2}, & n\equiv 2\bmod{3} \end{cases} $$ exist (with an ...
-4
votes
1answer
35 views

No solution in naturals

Prove that there is no pair $(x,y)$ of positive integers such that $$axy-b=x(x-c)+y(y-d)$$ where $a,b,c,d$ are positive integers such that $a>b>(\frac{1}{2} \cdot max\{c,d\})^2$.
1
vote
0answers
19 views

How is calculated the density of the 2-almost primes sequence?

According to the definition of sequence density at Wolfram's site: Let a sequence $\{a_i\}_{(i=1)}^{\infty}$ be strictly increasing and composed of non negative integers. Call $A(n)$ the number of ...
0
votes
1answer
45 views

Characterize the integers $a,b$ satisfying: $ab-1|a^2+b^2$

Let $a$ and $b$ be two positive integers such that $ab-1|a^2+b^2$. Show that $\frac{a^2+b^2}{ab-1}=5$.
0
votes
0answers
25 views

Fractions ( k / p - k ) ≠ prime/prime imply gcd(k / p - k) = 1

Prove that for every $$k ∈ \{{ 1, 2, 3, ..., \frac{(p - \frac{1 - (-1) ^ p}{2} )}{2}}\}\E $$(E is the set of even numbers) such that $$\frac{k}{p - k} \neq \frac{prime}{prime}$$ implies that for all k ...
1
vote
1answer
37 views

How to split congruences so moduli are prime powers?

If I have the linear congruence x=5 mod 84, is this equal to x=2 mod 3, since 3|84? This seems too easy.
1
vote
0answers
20 views

How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography. I have done some exercises with integers number but I have two exercises in which appears algebric ...
0
votes
0answers
40 views

congruence solution

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
4
votes
1answer
63 views

If $a$ is not divisible by $7$, then $a^3 - 1$ or $a^3 + 1$ is divisible by $7$

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
0answers
62 views

If $m =4^{n +1}$ with $n>0$ and m is prime then $3^\frac{m-1}{2}$ =-1(mod m)

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
1answer
30 views

Let p be a odd prime, If ord p (a) = h and h is even, then a^(h/2)= -1 mod p

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
1answer
18 views

Only one prime factor of $2^{2^{k}}-1$ of the form $3\pmod{4}$

Consider the number $N= 2^{2^{k}}-1$ for $k\geq 1$. Then is it true that for all $k \in \mathbb{N}$, $N$ has exactly one prime divisor which is $3 \pmod{4}$ and that being $3$. Some examples which I ...
-1
votes
0answers
24 views

Solutions to a congruence in a product of cyclic groups

I'm trying to answer the following question. How many solution are there for the equation $x\equiv 0 \pmod p$ in $\mathbb{Z}_{p}\times \mathbb{Z}_{p^{3}}\times \mathbb{Z}_{p^{5}}$
2
votes
2answers
43 views

What function when given the inputs $x,y$ returns the given $z$? [closed]

What function when given the inputs $x, y$ returns the given $z$? When $x = 2, y = 10$, $z = 1$ When $x = 6, y = 10$, $z = 2$ When $x = 50, y = 70$, $z = 5$ When $x = 16, y = 17$, $z = 1$ When $x = ...
2
votes
1answer
21 views

Finding quotient and remainder for a division

We are starting with division and congruence in my algebra course... this is one of the first exercises for the division algorithm. I've done the first that were given with fixed values but now I have ...
2
votes
4answers
63 views

Proving divisibility for $256 \mid 7^{2n} + 208n - 1$

I can't come up with a way of proving this: $$256 \mid 7^{2n} + 208n - 1\\ \forall n \in \Bbb N$$ I've tried by induction but couldn't see when to apply the inductive hypothesis... $$P(n+1) = ...
1
vote
1answer
15 views

Euclidean algorithm for dividing two products.

Say I have numbers, $a$ and $b$ represented as two products $$a = \prod_{i=0}^{N_a} a_i \hspace{1cm} b = \prod_{i=0}^{N_b}b_i$$ I do know $\{a_k\}$ and $\{b_k\}$ but can not store $a$ or $b$ in a ...
3
votes
1answer
51 views

What is the least positive integer $n$ for which $n!$ is divisible by $3^8$?

What is the least positive integer $n$ for which $n!$ is divisible by $3^8$? I am not sure how to tackle this problem without just putting in random low digits as $n$.
1
vote
1answer
33 views

Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$

I need help with this problem: Find all $n \in \Bbb Z$ such that $n^2 + n + 1$ divide $n^3-22$. I've got to a point where I know that $n^2 + n + 1 | -21$. So it should be among {${-21, -7, -3, -1, ...
0
votes
1answer
68 views

How many times is $n=(l+1)(m+1)$ generated while progressing through $l,m \in \{1,…\}$?

The sequence $n = (l+1)(m+1)$ for $l,m \in \{1,...\}$ yields exactly all non-prime (compound) numbers $n$. In general each non-prime number in this way is yielded $M(n)$ times. What is $M(n)$? I came ...
1
vote
1answer
71 views

Show that $x^3 + y^3 + z^3 + t^3 = 1999$ has infinitely many integer solutions.

Show that $x^3 + y^3 + z^3 + t^3 = 1999$ has infinitely many integer solutions. I have not been able to find a single solution to this equation. With some trial I think there does not exist a ...
3
votes
3answers
62 views

Find $(m,n)$ where $m$ and $n$ are positive integers.

Find all positive integers $m$ and $n$, such that: $$\frac 1m + \frac 1n - \frac 1{mn}=\frac 25$$ Actually, I have already solved this problem using inequality. The solutions I have found are: ...
2
votes
1answer
81 views

Prove that $(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$ is divisible by $(a+b+c)^{3}-a^{3}-b^{3}-c^{3}$

Prove that $$(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$$ is divisible by $$(a+b+c)^{3}-a^{3}-b^{3}-c^{3},$$ where $a,,b,c -$ integers, such that $(a+b+c)^{3}-a^{3}-b^{3}-c^{3}\not =0$ My ...
1
vote
2answers
29 views

Common divisor theorem?

I am reading Apostol's Mathematical analysis 2nd edition, and i am confused about theorem 1.6. ...If d|a and d|b, we say d is a common divisor of a and b... Theorem 1.6 Every pair of ...
4
votes
2answers
280 views

Sum of squares of integers divisible by 3

Suppose that $n$ is a sum of squares of three integers divisible by $3$. Prove that it is also a sum of squares of three integers not divisible by $3$. From the condition, ...
1
vote
1answer
19 views

Determine amount multiplied in sum

Suppose you have n , and r (result) = some value less than n (ltn) multiplied by 4, plus what's left of n after subtracting ltn (n - ltn). Eg. n = 60; (r) = 25 (ltn) + (60 (n) - 25 (ltn) = 35) = 135. ...
3
votes
4answers
65 views

Fermat's little theorem question: why isn't $a^p \equiv 1$?

Fermat's little theorem says that $a^p \equiv a \pmod p$. I have kind of a stupid question. Since $p \equiv 0\pmod p $, why isn't $a^p \equiv a^0 \equiv 1 \pmod p$ ?
1
vote
1answer
44 views

Let $m \in N$ and suppose that $p = 4m + 1$ is a prime number. Show that for any divisor $d$ of $m$ we have $(d/p) = 1$

I am stuck in this question: Let $m \in N$ and suppose that $p = 4m + 1$ is a prime number. Show that for any divisor $d$ of $m$ we have $(d/p) = 1$ (this is Legendre symbol) So far from Euler's ...
1
vote
2answers
141 views

Infinite Product $\prod_n^\infty \frac{1}{1-\frac{1}{n^s}} \rightarrow$?

Can this $$P_n(s)=\prod_{m=2}^n \frac{1}{1-\frac{1}{m^s}}$$ for s>1 and $\lim_{n\rightarrow\infty}$ be written any simpler (does it converge)? When $m$ runs here only over the primes this is the ...
2
votes
1answer
75 views

Is there an equivalent to the Bertrand's postulate between factorials and primorials?

As the title explains, I am trying to know if there is a definition about the upper limit to find the first primorial $p_i\#$ (following the definition at OEIS) existing after a given factorial $n!$ ...
0
votes
3answers
35 views

Find a surjection $(\mathbb Z/m)^\times\to (\mathbb Z/n)^\times$

Assume $n|m$ and suppose further that $m$ and $n$ have the same prime factors. How can we construct a surjective map $$(\mathbb Z/m)^\times\to (\mathbb Z/n)^\times$$ which preserves the group ...
1
vote
5answers
43 views

Stuck : Using inverses to solve linear congruences?

Question : What are the solutions of the linear congruence 3x ≡ 4 (mod 7)? Step 1 - We know that −2 is an inverse of 3 modulo 7. Step 2 - Multiplying both sides of the congruence by −2 shows that ...
1
vote
2answers
82 views

Any digit written $6k$ times forms a number divisible by $13$

Any digit written $6k$ times (like $111111$, $222222222222222222222222$, etc.) forms a number divisible by $13$. (source: a solution taken from careerbless) I tested with many numbers and it ...
-3
votes
0answers
35 views

few elementary questions in Number Theory [on hold]

I have a few questions in Number Theory: if $a​≡k^2$ and $gcd (a,p)=1$ then is $gcd(k^2, p)=1$? when can I "divide" a congruence and say that it is equivalence to the original congruence? for ...
-1
votes
2answers
36 views

Prove that $(\mathbb Z/m\mathbb Z)^\times$ is cyclic if and only if there is a primitive root modulo $m$

Prove that $(\mathbb Z/m\mathbb Z)^\times$ is cyclic if and only if there is a primitive root modulo $m$. if $g$ is a primtive root modulo $m$ so indeed $(\mathbb Z/m\mathbb Z)^\times$ is cyclic by ...
1
vote
2answers
31 views

Problem in proof of: Show that inverse of 'a' modulo 'm' exist if 'a' and 'm' are relative primes and 'm'>1?

From K Rosen's Discrete Maths, Theorem: If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (That is, there is a ...
2
votes
0answers
76 views

Any natural number n can be expressed as $n = 2^a \cdot b$ where $b$ is odd. Function such that $f(n) = a$

Given that any natural number $n$, can be expressed $n = 2^a \cdot b$ where $b$ is odd. Is there a function that does not include modulo or floor functions that satisfies $f(n) = a$? Thus far I have ...
0
votes
0answers
6 views

Exponential sum over $(\mathbb{Z}/(p^t))^*$

Let $p$ be a prime and $t$ a natural number. Let us denote $(\mathbb{Z}/(p^t))^*$ to the group of units of $\mathbb{Z}/(p^t)$. I have the following exponential sum $$ S = \sum_{w \in ...
13
votes
3answers
1k views

How to solve this algorithmic math olympiad problem?

So, today we had a local contest in my state to find eligible people for the international math olympiad "IMO" ... I was stuck with this very interesting algorithmic problem: Let $n$ be a natural ...
0
votes
3answers
33 views

Which is not a primitive root?

If p is an odd prime then $6$, $10$ and $15$ cannot all be primitive roots. My question is this: Why can't all three (simultaneously) be a primitive root modulo $p$? I have no idea why this is the ...
3
votes
2answers
57 views

Prove that if $2n+1$ and $3n+1$ are both perfect squares then $40|n$.

Prove that if $2n+1$ and $3n+1$ are both perfect squares then $40|n$. First, I took $$2n+1 \equiv x^2 \equiv 0, 1 \pmod 4$$ which showed that $n$ was even. Now, $$3n + 1 \equiv y^2 \equiv 0, 1, ...
3
votes
1answer
29 views

If for $p \in \Bbb P$ and $x,y,z \in \Bbb N$ we have $x^{p-1}+y^{p-1}=z^{p-1}$, then $p\mid xyz$

I want to prove the statement in the title. This is, how far i came: Proof. We have $p \in \Bbb P$ and $x,y,z \in \Bbb N$ with $x^{p-1}+y^{p-1}=z^{p-1}$. If $p=2$, we have $x+y=z$. Now if $x$ and ...
0
votes
0answers
13 views

numbers x such that the sum of the divisors is a perfect square [duplicate]

Hello I am reading "The Theory of Numbers, by Robert D. Carmichael" and stuck in an exercise problem, Find numbers x such that the sum of the divisors of x is a perfect square. I know sum of ...
0
votes
0answers
23 views

Find all pairs positive integers $m,n>1$, such that $(mn-1)|(n^3-1)$ [duplicate]

Find all pairs of positive integers $m,n>1$, such that $$(mn-1)|(n^3-1)$$ My work so far: 1) If $m=n^2$, then $(mn-1)=(n^3-1)|(n^3-1)$. Then $(m,n)=(n^2,n) -$ solution. 2) $(mn-1)|(n^3-1) ...
1
vote
1answer
21 views

How many positive pairof integral values (x,y) exist which satisfy $2xy-4x^2+12x-5y=11?$

How many positive pairof integral values (x,y) exist which satisfy $2xy-4x^2+12x-5y=11?$ My attempt: $y=(4x^2-12x+11)/(2x-5)=\dfrac{(4x^2-10x)-(2x-5)+6}{2x-5}=2x-1+6/(2x-5)$ For any such pair ...