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

learn more… | top users | synonyms (1)

1
vote
0answers
31 views

Integer Factorization problem - New Idea

I been thinking about slightly different approach of solving the problem, and I want you to tell me if my idea is reasonable and if it's original(If someone already thought about this, I would be ...
0
votes
1answer
9 views

Proof using Division by GCD

Let $a,b,c \in\mathbb Z$ where $a \neq0$ or $b \neq 0$. Suppose that $c \neq 0$ and is a common divisor of $a$ and $b$. Prove that: ${gcd(a,b)\over |c|}= gcd ({a \over c}, {b \over c})$ What I ...
1
vote
2answers
37 views

Arrangement of points in a circle

From the 2015 Moscow Mathematical Olympiad: The numbers $1$ to $1000$ are arranged on a circle such that each number divides the sum of its two neighbors. Suppose that the number $k$ has two odd ...
3
votes
2answers
66 views

$\sqrt{13a^2+b^2}$ and $\sqrt{a^2+13b^2}$ cannot be simultaneously rational

Let $a,b \in \mathbb{N}^{*}$. Prove that $\sqrt{13a^2+b^2}$ and $\sqrt{a^2+13b^2}$ cannot be simultaneously rational. If $(a,b)=(k,k\cdot6)$, then $\sqrt{13a^2+b^2}$ is rational, but I do not know if ...
10
votes
0answers
54 views

Numbers that are clearly NOT a Square

Although I have never studied math very seriously, I have heard of Brocard's Problem, which asks for integer solutions for the following Diophantine Equation:$$n!+1=m^2$$ The only solutions are ...
1
vote
1answer
70 views

A problem of decimals..

The exact problem: For any natural number n>1, write the infinite decimal expansion of $\frac{1}{n}$ (for example, we write 1/2 = $0.4\overline9$ as it's infinite decimal expansion, not 0.5). ...
5
votes
1answer
43 views

Prime factorization and hcf

For any given integer $n$, we prime factorize it as follows $$n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}. $$ Let $g = \gcd(k_1, k_2, \ldots, k_r)$ and $m_i = k_i / g$. The function $F$ is ...
1
vote
0answers
13 views

Is there K and an infinite amount of different primes $a_i,b_i$ so that min|$a_i^y-b_i^x$| <K on natural x,y for all i?

First of all I know that it was proved recently that prime gaps are less than like 7 million for an infinite amount of primes, but I'm not smart enough to follow the proof. I am looking for a ...
0
votes
0answers
16 views

Is $\sigma(2^r)$ a palindrome (in base $10$) for some $r > 2$, where $\sigma$ is the sum-of-divisors function?

(Note: This post is a bit related to this earlier MSE question.) The title says it all. Is $\sigma(2^r)$ a palindrome (in base $10$) for some $r > 2$, where $\sigma$ is the sum-of-divisors ...
8
votes
4answers
122 views

Is there $n$ such that $n,n^2,n^3$ start with the same digit ($\neq 1)$

From the 2015 Moscow Mathematical Olympiad: Is there some $n>2$ such that $n,n^2$ and $n^3$ start with the same digit (this digit being different from $1$) Using a computer I found that $99$ ...
18
votes
1answer
127 views

Is there any palindromic power of $2$?

My question is in the title: Is it possible to find $n≥4$ such that $2^n$ is a palindromic number (in base $10$)? A palindromic number is a number which is the same, independently from which ...
-4
votes
0answers
35 views

Number Theory - Prime Factorization and hcf of prime powers [on hold]

For any given integer n, we prime factorize it as follows $$n = p_1^{k_1} · p_2^{k_2} · … · p_r^{k_r}. $$ Let g = gcd$(k_1, k_2, … k_r)$ and $m_i = k_i / g. $ The function F is defined as: $$F(n) = ...
0
votes
1answer
22 views

I Need A Good Book On Elementary Algebra and analysis.

I am trying to study a course with course code MTH230 (Elementary algebra and analysis). The course outline are: Set theory Cartesian product Mappings Peano's axiom Construction of integers & ...
1
vote
2answers
18 views

How do i find three successive natural odd numbers for which the sum of their squares can be written in decimal system as :$\overline{xxxx} $? [on hold]

let $a, b,c$ be a successive natural odd numbers, I would like to know how do i find three successive natural odd numbers for which the sum of their squares : $a²+b²+c²$ can be written in decimal ...
2
votes
2answers
54 views

Find all $n$ such that $\varphi(n) \equiv 2 \pmod 4$ [on hold]

My question is Find all $n$ such that $\varphi(n) \equiv 2 \pmod 4$, where $\varphi(n)$ is the Euler totient function. I am no where to start so any hint or help ? and if we are given such a ...
0
votes
0answers
49 views

Number of integral solutions to $y_1 + y_2 + y_3 + y_4 =30$ with $y_i \ge 2$

How many solutions there are to the given equation that satisfy the given condition: $y_1 + y_2 + y_3 + y_4 =30$, each $y_i$ is an integer that is at least $2$. I don't know how to start this ...
0
votes
0answers
72 views

Sum of all rational numbers up to infinity [on hold]

Based on the well known sum of natural numbers where $$\sum_{n=1}^\infty n=-\frac{1}{12}$$ Does it make sense to say that the sum of all rational number is zero? How to come with this? Simply take ...
1
vote
1answer
68 views

Prove or reject: if $a^2|b^3$ then $a|b$

I tried to find a counter example but failed!! If $a^2|b^3$ then it is obvious that $a|b^3$ because $b^3=ka^2=(ka)a=k'a$ but we hardly can say $a|b$
4
votes
4answers
105 views

Let $S = \{n\in\mathbb{N}\mid 133 \text{ divides } 3^n + 1\}$. Find three elements of S.

Question: Let $S = \{n\in\mathbb{N}\mid 133 \;\text{divides} \; 3^n + 1\}$ $a)$ Find three different elements of $S$. $b)$ Prove that $S$ is an infinite set. My intuition is find the prime factors of ...
0
votes
1answer
63 views

I need a best proof that e is a transcendental? [on hold]

Where can I find the best proof that $e$ is transcendental?
0
votes
1answer
40 views

If $p = a^2 + b^2$, prove that $(ab^{-1})^2 \equiv -1 \pmod{p}$

Let $p \equiv 1 \pmod{4}$ be a prime, where $p = a^2 + b^2$. Show that $(ab^{-1})^2 \equiv -1 \pmod{p}$ I'm having trouble with this question. Any help is appreciated.
0
votes
1answer
44 views

Does the product of two numbers with a primitive representation have a primitive representation?

I know the theorem that $n = x^2 + y^2, \, \textrm{gcd}(x, y) = 1 \iff p | n \implies p \equiv 1 \bmod 4$. We call an expression of $n$ in this form primitive. I'm trying to prove the statement. I've ...
1
vote
1answer
45 views

Each alphabet of KANGAROO is replaced with number by $2$ people; which alphabet is replaced with the same number?

In the word KANGAROO Bill and Bob replace the letters by digits, so that the resulting numbers are multiples of $11$. They each replace different letters by different digits and the same letters by ...
1
vote
1answer
43 views

$4\times ABCDE = EDCBA$: Four times a five digit integer is that integer backwards.

A student gave me this puzzle the other day. Where $A,B,C,D,E$ are distinct digits, and where $A,E\ne0$, what 5 digit integer satisfies the condition below? $$4\times ABCDE=EDCBA$$ What I'm ...
0
votes
2answers
28 views

Transitivity for sets.

Suppose one has $f(A)=D_0$ and $f(D_{n})=D_{n+1}$, where f is a 1-1 function. Furthermore, $D_{n}\subset D_{n-1}\subset A$. Take $D = \cap_{n=0}^\infty D_n$ but $D\not=\emptyset$. (I changed part of ...
1
vote
1answer
100 views

Determine all $k$ such that $k^3+k+1$ is divisible by 11

The task is the following: Determine all $\ k\in\mathbb Z$ such that $k^3+k+1$ is divisible by 11 I assumed that "$k^3+k+1$ is divisible by 11" is saying $11|k^3+k+1$. That means I can rewrite it as ...
0
votes
1answer
20 views

Proving Linear Independence Given Odd Absolute Values

With three vectors $a,b,c \in \mathbb{R}^3$, the magnitude of a$,b,c,a-b,b-c$, and $c-a$ are all odd integers (not necessarily distinct). How could you prove the three vectors are linearly ...
3
votes
3answers
63 views

Compute a natural number $n\geq 2$ s.t. $p\mid n \Longrightarrow p^2\nmid n$ AND $p-1\mid n \Longleftrightarrow p\mid n$ for all prime divisor p of n.

Question: Compute a natural number $n\geq 2$ that satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide $n$. For each prime number $p$, $p-1$ divides $n$ if and only if $p$ divides ...
1
vote
1answer
41 views

Show that if p is an odd prime, with p $\equiv 3 \pmod 4$ then $(\mathbb{Z}^*_{p})^4$ = $(\mathbb{Z}^*_{p})^2$.

Show that if p is an odd prime, with p $\equiv 3 \pmod 4$, then $(\mathbb{Z}^*_{p})^4$ = $(\mathbb{Z}^*_{p})^2$. Any help is appreciated.
0
votes
3answers
51 views

$n$ such that $9$ divides $(n+3)(n-3)(n+1)(n-1)(n-100)$

How should one systematically proceed to find $n \in \mathbb{Z}$ such that $9$ divides $(n+3)(n-3)(n+1)(n-1)(n-100)$? Equivalently, how does one solve the following congruence? ...
1
vote
0answers
13 views

Show that there exists $\alpha,\beta\in\mathbb{Z}^*_{n}$ [duplicate]

Let $n = pq$ where $p$ and $q$ are distinct, odd primes. Show that there exists $\alpha,\beta\in\mathbb{Z}^*_{n}$ such that $\alpha$ and $\beta$ are not elements in $(\mathbb{Z}^*_{n})^2$, and ...
2
votes
2answers
38 views

Is it correct to say gcd$(r, 0)$? The definition says greatest common divisor of nonzero integers.

Source: Discrete Mathematics with Applications, Susanna. S. Epp In the definition of greatest common divisor of $a$ and $b$: $a$ and $b$ in gcd$(a, b)$ are nonzero integers, so why it follows in ...
1
vote
1answer
20 views

euclidean algorithm iteration problem

So if I have a congruence of the form $ad \equiv 1 \mod m$, where $a$, $d$, $m$ are all integers and $m > a$, I should be able to find the integer $d$ satisfying the congruence using the Euclidean ...
6
votes
4answers
112 views

Solve equation $\frac{1}{x}+\frac{1}{y}=\frac{2}{101}$ in naturals

My try was $$\frac{1}{x}+\frac{1}{y}=\frac{x+y}{xy}=\frac{2}{101}\\x+y=2k,xy=101k\\x=2k-y\\y(2k-y)=101k\\2ky-y^2=101k\\y^2-2ky+101k=0\\y=k+\sqrt{k^2-101k}\\x=k-\sqrt{k^2-101k}$$ Now $\sqrt{k^2-101k}$ ...
0
votes
0answers
28 views

speed of divergence of $\prod_{m=1}^n (\frac{z}{m} + 1)^m$

I would like to find the speed of divergence of $\prod_{m=1}^n (\frac{z}{m} + 1)^m$ for any $z$. For example, if $|z| < 1$, doing taylor expansion we know that it is roughly $e^{zn}.$ But I need it ...
0
votes
2answers
36 views

How is unique factorization of integers related to computing greatest common divisors?

Source: Discrete Mathematics with Applications, Susanna S. Epp. What does the unique factorization of integers have to do with gcd $2^{10}$ of ($10^{20}, 6^{30}$) in Example 4.8.5.b? ...
0
votes
1answer
46 views

Number theory, a question about finite product [on hold]

Let $a_1, a_2,a_3,a_4,a_5$ be five different integers, such $$(6-a_1)(6-a_2)(6-a_3)(6-a_4)(6-a_5)=45,$$ how could I know what is the value of the sum $a_1+a_2+a_3+a_4+a_5$? What is the link between ...
2
votes
0answers
20 views

Term for maximal proper divisors

What do you call a divisor, $d$, of a number $n$ which is of the form $d = n/p$ where $p$ is a prime divisor of $n$? For a cryptography class I need to discuss such numbers (to describe how to find ...
0
votes
1answer
33 views

Is/when is this property about the totative subset of $(\mathbb{Z}_n , +_n)$ true?

Is it possible to show (or when is it true); that for the group $\mathbb{Z}^+_n :=(\mathbb{Z}_n , +_n) $, there exists an $a \in \mathbb{Z}^+_n$ for each $z \in \mathbb{Z}^+_n$, where both $z+_n a$ ...
0
votes
1answer
36 views

If $\gcd(a,b)=D$, then why must there exists integers $x$ and $y$ such that $ax+by=D$? [on hold]

If the greatest common divisor of two integers $a,b$ is $D$, then why must there exists two integers $x,y$ such that $ax+by=D$?
18
votes
4answers
3k views

Prove that 10101…10101 is NOT a prime.

So basically we have a number $10101...10101$ that contains $2016$ zeros and can be written as$ \sum _{ k=0 }^{ 2016 }{ 100^{ k } }$ . I want to prove that this number is not a prime without using ...
2
votes
0answers
24 views

Is always two times an even semiprime at a distance $1$ or prime to the closest previous odd semiprime?

This is an observation regarding the semiprimes, also named 2-almost primes, biprimes, or the product of two primes. This week I do not have a computer, only a tablet (hospitalized with a lot of free ...
2
votes
0answers
24 views

Choosing three integers to satisfy an equation under a specific condition

Find three integers $(a,b,c)$ such that: $x*a + y*b + z*c = a + b$ only when $x = 1, y = 1, z = 0$ where $x, y$ and $z$ can be chosen as any non-negative integers. For example, choosing $a = 1$; $b = ...
1
vote
0answers
53 views

Test if a number is in ${\mathbb R}$ [on hold]

Given a number $x$ $\in$ ${\mathbb R}$ is there a way to know if $x$ $\in$ ${\mathbb N}$ without comparing $x$ with a number in any known list of numbers? (ex. {0,1,2,3,...}) To be more specific: ...
8
votes
3answers
378 views

Decimals of the square root of $n$.

Let $a_1, \ldots, a_k$ be any sequence of digits (i.e., each $a_i$ is between 0 and 9). Prove that there exists an integer $n$ such that $\sqrt{n}$ has its first $k$ decimals after the decimal point ...
4
votes
0answers
29 views

Proving the congruence of a Fibonacci Number [on hold]

Let $F_n$ denote the $n^{th}$ fibonacci number where $F_0 = 0, F_1 = 1$. Prove that for all primes $p > 5$, $$F_p \equiv 5^{\frac{p-1}{2}} \mod (p)$$
0
votes
2answers
36 views

To find composite integers satisfying the given property.

Find all positive composite integers $n$ greater than $1$ such that for any relatively prime divisors $a$ and $b$ of $n$ with $a > 1$ and $b > 1$, the number $ab-a-b+1$ is also a divisor of $n$. ...
2
votes
3answers
64 views

Alternative Proof that $\sqrt{p}$ is Irrational when $p$ is Prime

I have found various proofs that $\sqrt{p}$ is irrational on this site, but I didn't find one similar to the one that I am about to post, so I am wondering if it is free of logical problems. Here is ...
0
votes
1answer
80 views

Ideals of $ord$

Let $p$ be a prime number in $\mathbb{Z}$. Let $R = R_p = \{x \in \mathbb{Q}\ |\ ord_p(x)\geq0\}$, which is a subring of $\mathbb{Q}$. (a) Show that the only nonzero ideals of $R$ are the ...
3
votes
0answers
30 views

Properties of the Discrete Logarithm Problem

I am self-studying Hoffstein's An Introduction to Mathematical Cryptography, and this is problem 2.3 (p. 107-08). Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ with order $r$. ...