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

learn more… | top users | synonyms (1)

1
vote
3answers
169 views

Repeatedly summing the digits of a number

Take an arbitrary number - for the sake of an example, I'll use 392. If we add the digits, we get 3 + 9 + 2 = 14, and then add those digits to get 5 (keep adding the digits of each result until it ...
1
vote
3answers
63 views

There exist infinitely many natural numbers $a$, such that for any natural number $n$, the number $z=n^4 + a$ is a composite number.

There is this problem that I tried but there are still some questions, confusions and doubts. There exist infinitely many natural numbers $a$, such that for any natural number $n$, the number $z=n^4 ...
1
vote
2answers
61 views

Show $\gcd (a,b)=\gcd (b,r)$ if $a = bq + r$

Let $a, b$ be two integers with $b \neq 0$, and $q, r$ non-negative integers such that $a = bq + r$. How can we show that $\gcd (a,b)=\gcd (b,r)$?
1
vote
2answers
274 views

Proof - There're infinitely many primes of the form 3k + 2 — origin of $3q_1..q_n + 2$

Origin — Elementary Number Theory — Jones — p28 — Exercise 2.6 To instigate a contradiction, postulate $q_1,q_2,\dots,q_n$ as all the primes $\neq 2 (=$ the only even prime) of the form $3k+2$. ...
1
vote
2answers
89 views

Given: $\operatorname{gcf}(x,36)=9$ and $\operatorname{lcm}(x,36)=108$. Find $x$.

Given: $\operatorname{gcf}(x,36)=9$ and $\operatorname{lcm}(x,36)=108$. Find $x$. p.s I tried $54$ but although the $\operatorname{lcm}$ of $54$ and $36$ is $108$ the GCF is $18$ and it has to be ...
1
vote
2answers
105 views

Find a permutation of this expression to obtain a maximum possible value

Find a permutation $a_1, a_2, ..., a_{1001}$ of the numbers $1,2,...,1001$ such that the expression $$a_1^{a_2^{a_3^{...^{...^{a_{1001}}}}}}$$ take a maximum possible value.
1
vote
5answers
85 views

Proving that a number is composite

I have proved that the number $10^{5}2^{17}+1$ is composite by showing that it is divisible by 3 , using remainders. I want an alternative proof.I am looking for a very elementary proof that does not ...
1
vote
2answers
154 views

Let $a, b, n$ be elements of $\mathbb N $ such that $ a^n\mid b^n $. Show that $a\mid b$. [closed]

Let $a, b, n$ be elements of $\mathbb N$ such that $ a^n\mid b^n $. Show that $a\mid b$. [P.S. Use the axioms of natural numbers.] Are we using the properties of divisibility and afterwards ...
1
vote
2answers
96 views

Multiplicative inverses for $Z_n$

Whilst reading I came across the strange claim that multiplicative inverses exist for only prime values of $n$ in $Z_n$. I am a little puzzled as contrary to that, I know that additive inverses exist ...
1
vote
4answers
154 views

Common factors for all palindromes

For example a palindrome of length $4$ is always divisible by $11$ because palindromes of length $4$ are in the form of: $$\overline{abba}$$ so it is equal to $$1001a+110b$$ and $1001$ and $110$ are ...
1
vote
3answers
629 views

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$. I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then ...
1
vote
2answers
83 views

Show that $x^3+y^3 = 3\mod 9$ has no solutions

Not even sure how to go about this. I tried $x^3 = 3-y^3 \mod 9$, but not sure what that does.
1
vote
2answers
81 views

About Pythagorean triple

I have a question about number of primitive Pythagorean triples. Is there infinite number of primitive Pythagroean triples for which the acute angles of the corresponding triangles are, for any given ...
1
vote
2answers
539 views

Product of quadratic residues mod p $\equiv 1$ mod p iff $p \equiv 3$ mod 4

Let $p$ be an odd prime number. Prove that the product of the quadratic residues modulo $p$ is congruent to $1$ modulo $p$ if and only if $p \equiv 3 \pmod 4$. I've tried using the fact that any ...
1
vote
2answers
70 views

${{p^k}\choose{j}}\equiv 0\pmod{p}$ for $0 < j < p^k$

$${{p^k}\choose{j}}\equiv 0\pmod{p}.\ \ \ \text{for $0 < j < p^k$ and p is prime}$$ I can show this for $k=1$ using the fact that in denominator all numbers are less than $p$. I need hint ...
1
vote
1answer
425 views

What is an “incongruent” solution?

For example, "Solve the congruence (if possible), listing all the incongruent solutions:" $$561x\equiv 3575\mod{1562}$$ I found $x\equiv 37+142t,\ 0\leq t\leq 10,\ t\in\mathbb{Z}$... There are 11 ...
1
vote
1answer
50 views

Properties of Digit root

Why the digit root of any number calculated in any way remains same...e.g Let $f(x)$denote the digit root of $x$ $f(1237)=f(12+37)=f(49)=f(123+7)=f(130)=4$ I checked numerically with many numbers ...
1
vote
2answers
39 views

Show $a^2=6k+3 \Rightarrow a = 6n + 3$

Show that if $a^2=6k+3$, for some integer $k$, then also $a = 6n + 3$ for an integer n. Or in in other words: $a^2=6k+3 \Rightarrow a = 6n + 3$. Taking the square root, $a=\sqrt{6k+3}$ does not ...
1
vote
2answers
39 views

Simple notation question

Let A = {2, 3, 4, 6, 7, 9} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 3 | (x − y). Then 2 R 2 because 2 − 2 = 0, and 3 | 0. What does the ...
1
vote
3answers
470 views

Suppose that $p$ ≥ $q$ ≥ $5$ are both prime numbers. Prove that 24 divides ($p^2 − q^2$)

I suppose I need to use prime factorization. I want to show $p^2-q^2=24k$ for some integer $k$ . How can I start this proof?
1
vote
1answer
167 views

Every $n > 17$ is a non-negative integer combination of $4$ and $7$. [duplicate]

Prove that every integer greater than $17$ is a non-negative integer combination of $4$ and $7$. In other words, for all natural numbers $n$, $n$ greater or equal to $17$, there exists non-negative ...
1
vote
2answers
82 views

What conclusion can we draw?

Let $f \colon Z \to \{-1, 1\}$, where $Z$ denotes the set of integers, be defined by $ f(n) = 1$ if $n$ is even and $f(n) = -1$ if $n$ is odd. Then we can easily show that $f(m+n) = f(m) \cdot f(n)$ ...
1
vote
1answer
50 views

Finding the base in which $54/4=13$ is a true statement

I was given for a homework assignment: $$\frac {54} 4 = 13$$ The goal is to find the base of the three numbers (they share the same base), I was given the answer by the TA of 6, but I didn't learn ...
1
vote
1answer
96 views

Congruences: Exponent cancelation law?

Is this valid? If $a^n \equiv b^n \pmod n \Rightarrow a \equiv b \pmod n $
1
vote
1answer
179 views

Linear equation with prime coefficient.

Suppose we have a linear equation with two variables say $x$ and $y$ and three integer coefficient $a , b$ and $c$ (constant), where $a$ and $b$ are prime all are greater than zero. $ax+by=c$ how ...
1
vote
2answers
54 views

How many fourth powers are below $n^2$?

Given $n^2$, how many fourth powers $(x^4)$ are between 0 and $n^2$? $n,x\in \mathbb{Z}$ Does this just reduce down to how many squares are below $n$?
1
vote
1answer
40 views

If $ p \equiv 1 \pmod{4}$, prove $((\frac{p-1}{2})!)^2 \equiv -1 \pmod {p}$ where p is prime.

Characteristics: The fields where $ p \equiv 1 \pmod{4}$ has half the number from 1 to $\frac{p-1}{2}$ both in positive and the negative. There can be paired up such that when multiplied together, ...
1
vote
4answers
179 views

$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow ...
1
vote
5answers
278 views

$24\mid n(n^{2}-1)(3n+2)$ for all $n$ natural problems in the statement.

"Prove that for every $ n $ natural, $24\mid n(n^2-1)(3n+2)$" Resolution: $$24\mid n(n^2-1)(3n+2)$$if$$3\cdot8\mid n(n^2-1)(3n+2)$$since$$n(n^2-1)(3n+2)=(n-1)n(n+1)(3n+2)\Rightarrow3\mid ...
1
vote
1answer
69 views

Is there a proof that no lower bound exists for the totient function?

I read here that there is no lower bound for the totient function. Is there a proof of that?
1
vote
4answers
147 views

Prove that $\gcd(x, y)=\gcd(x,ax+y)$, would this be the correct reasoning?

We know that $\gcd(x, y) = d$ as d divides $x$ and $y$, now suppose there are $x'$ and $y'$ integers such that $$x = d \cdot x' \implies d|x \\y = d \cdot y' \implies d|y$$ then $a \cdot x$ would ...
1
vote
3answers
147 views

Prove that MCD is 1 or 3 knowing (a,b) = 1

I'm don't know from where to start in this problem. I have to prove that $(a+b,a^2-ab+b^2)=1 \text{ or } 3$ knowing that $(a,b) = 1$. I've tried using the method they taught us on class, so ...
1
vote
2answers
100 views

Show that $\sum\limits_{p \leq x} \frac{1}{p}$ ~ ${\log\log{x}}$ when ${x \to \infty}$ (here p is a prime)

I saw that some of you were upset over my last question, so I decided to ask a more interesting question: Show that $\sum\limits_{p \leq x} \frac{1}{p}$ ~ ${\log\log{x}}$ when ${x \to \infty}$ (here ...
1
vote
3answers
415 views

The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number?

I am stuck on the following problem: The smallest positive integer in the set $\{24u+60v+200w : u,v,w \in \Bbb Z\}$is given by which of the following number? The options are: ...
1
vote
3answers
61 views

Conjecture on combinate of positive integers in terms of primes

Along a heuristic calculation, I am struggeling with a possible proof for my following conjecture: Every positive integer $n\in \Bbb N$ can be written as a unique combination of $a,b \in \Bbb N$, ...
1
vote
6answers
222 views

Solving a Linear Congruence

I've been trying to solve the following linear congruence with not much success: 19 congruent to $19\equiv 21x\text{ (mod }26)$ If anyone could point me to the solution i'd be grateful, thanks in ...
1
vote
2answers
142 views

Is $\gcd(a,bc)=\gcd(a,b)\gcd({a\over\gcd(a,b)}, c)$?

Is it true that $\gcd(a,bc)=\gcd(a,b)\gcd({a\over\gcd(a,b)}, c)$? It is true in quite a few examples that I came up with, e.g. $a = 18, b = 21, c = 33$ $\gcd(18,21)\gcd({18\over\gcd(18,21)}, ...
1
vote
2answers
976 views

Prove that $5^n - 2^n$ is divisible by $3$ for all nonnegative integers $n$ using mathematical induction [duplicate]

Using mathematical induction, prove for all integers n 1 that $5^n - 2^n$ is divisible by 3. Can someone help me with this?
1
vote
4answers
50 views

Correlation between multiplied numbers?

I do not have a strong math background, but I'm curious as to what this pattern is from a mathematical standpoint. I was curious how many minutes there were in a day, so I said "24*6=144, add a 0, ...
1
vote
4answers
129 views

Can you have a numeral system with infinite digits?

If you were working in a number system where there was a one-to-one and onto mapping from each natural to a symbol in the system, what would it mean to have a representation in the system that ...
1
vote
2answers
141 views

Are the propreties of arithmetic unproven?

For example, the property which says that $$a(b+c)=ab+ac$$ This is very clear for integers, but is it actually provable for all real numbers (and complex maybe). Or the commutative property which says ...
1
vote
2answers
90 views

Prove if $(l,m)=1$ and $l\mid mn$, then $l\mid n$.

I just took my number theory final and this was on the exam as the second question. It said to use the canonical decomposition of $l, m$ and $n$ for the proof. This is what I put down on the exam: ...
1
vote
2answers
84 views

A new prime divides $a^p+1$

Let $a\in \mathbb{Z}$ and $p, q\in\mathbb{P}$. If $q\mid a+1$, there exists at least a prime $r \neq q$ such that $r\mid a^p+1$ (except for some trivial cases).
1
vote
3answers
248 views

Proving that every $x \in \mathbb Z_{20}$ satisfies $x^4 - 10x^2 + 9 \equiv 0 \mod 20$

Could you help me with the problem below? Prove that for every $x \in \mathbb{Z}_{20}$ we have $x^4 - 10x^2 + 9 \equiv 0 \mod 20$. Thank you.
1
vote
1answer
686 views

Proving that $C$ is a subset of $f^{-1}[f(C)]$

More homework help. Given the function $f:A \to B$. Let $C$ be a subset of $A$ and let $D$ be a subset of $B$. Prove that: $C$ is a subset of $f^{-1}[f(C)]$ So I have to show that every element ...
1
vote
2answers
189 views

Compute the $p$-adic order of $(p^n)! = p^n (p^n − 1) (p^n − 2) \cdots (2) 1$.

This is a question from a book I'm struggling with, please could you provide a clear proof? Compute the $p$-adic order of $(p^n)! = p^n (p^n − 1) (p^n − 2) \cdots (2) 1$. kind thanks
1
vote
5answers
195 views

To prove a property of greatest common divisor

Suppose integer $d$ is the greatest common divisor of integer $a$ and $b$, how to prove, there exist whole number $r$ and $s$, so that $$d = r \cdot a + s \cdot b $$ ? i know a proof in abstract ...
1
vote
3answers
170 views

Prove that if $g$ is a primitive root of $n$ and $g*b \equiv 1 \pmod n$, then $b$ is also a primitive root of $n$.

Some useful facts I am trying to use: If the multiplicative group $U_n$ modulo $n$ is a cyclic group, a generator $g$ of $U_n$ is called a primitive root of $n$. if $g$ in $U_n$ is a primitive ...
1
vote
2answers
299 views

Sum of integers divisible by their digits

Determine the sum of : all two-digit positive integers that are divisible by each of their digits. For example : $12$ is divisible by $1$ and $2$.
1
vote
3answers
158 views

Why are these two equivalent? (Modular multiplicative inverse)

According to Wikipedia's entry "Modular Multiplicative Inverse," $d\equiv e^{-1} \pmod {\phi(n)}$ and $ed\equiv 1 \pmod{\phi(n)}$ are equivalent. Why is this the case? Can someone provide a ...