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

learn more… | top users | synonyms (1)

-2
votes
0answers
24 views

Number of ways for product of integers

We are given two positive integers $n$ and $m$. How many ways to write $n$ as a product of $m$ positive integers written in a non-decreasing order ? For example If n=24 and m=1, 2, 3, 4, then the ...
0
votes
0answers
50 views

Sum of all rational numbers up to infinity

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 ...
0
votes
1answer
54 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
2answers
72 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
51 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
36 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
0answers
24 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
39 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
39 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
24 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
97 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
17 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
60 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 ...
0
votes
1answer
33 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
50 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
37 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
19 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
108 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
23 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
34 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
42 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 ...
1
vote
0answers
17 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
30 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
35 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 ...
1
vote
0answers
20 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
23 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
51 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
4answers
372 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
35 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
28 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$. ...
3
votes
1answer
49 views

Why is $x^2+1$ divisible by $10$ if $x$ has a $3$ or $7$ in the one's place?

So I have the simple polynomial $x^2+1$. If I plug in ANY number that has a $3$ or a $7$ in the ones place $x^2+1$ is divisible by $10$. Why? Is there a reason for this? So numbers like ...
0
votes
2answers
53 views

Proof Verification: If $x$ is a nonnegative real number, then $\big[\sqrt{[x]}\big] = \big[\sqrt{x}\big]$

Let $x$ be a nonnegative real number and denote $[x]$ as the greatest integer less than or equal to $x$. We will attempt to prove that $\big[\sqrt{x}\big] = \big[\sqrt{[x]}\big]$. First suppose that ...
0
votes
0answers
51 views

Hypothetical proof of Goldbach's conjecture? [on hold]

Goldbach's conjecture: Every even number greater than 4 is the sum of two prime numbers. An equivalent statement is; For all $n\geq 2$ there exists a number $e(n)$ such that $n-e(n)$ and ...
3
votes
0answers
64 views

Primes and irreducibles of $\{a+b\sqrt{-2}\ |\ a,b \in \mathbb{Z}\}$

Let $R = \{a+b\sqrt{-2}\ |\ a,b \in \mathbb{Z}\}$ Rational primes $p \geq 3$ of the form $p = a^2 + 2b^2$ factorize in $R$ as a >product of two irreducibles which are not associate. Such ...
0
votes
0answers
26 views

Is there a proof that $(n-2x)! \times n^{2x-1} > n!$ (where $x$ is a function related to the prime counting function

Is it possible to prove the following? Let $\pi$ be the prime counting function and $A(n)=\pi(2n)-\pi(n)$ $(n-2A(n))! \times n^{2A(n)-1} > n!$
4
votes
2answers
69 views

Prime counting function; when is it true that $\pi(n) > \pi(2n) -\pi(n)$?

Let $\pi$ be the prime counting function. Under what conditions is it proven true that $\pi(n) > \pi(2n) -\pi(n)$, if at all?
2
votes
1answer
20 views

How do you calculate the width of the Poset Lattice of Divisors?

Let $n = 10800 = 2^43^35^2$ I can find a set of eleven divisors of $n$ such that none divides another: $$\begin{array}{ccccc} & & & 2 3^3 & 3^35\\ & & 2^23^2 & ...
3
votes
1answer
37 views

Proof Verification: Show that $\Big[\frac{x+n}{m}\Big] = \bigg[\frac{[x]+n}{m}\bigg]$

Let $m,n \in \mathbb{Z}$ and let $x \in \mathbb{R}$. Let $[x]$ denote the floor function. We will attempt to prove $$\Big[\frac{x+n}{m}\Big] = \bigg[\frac{[x]+n}{m}\bigg]$$ Suppose without loss of ...
0
votes
2answers
40 views

How to check if a a relatively small number is prime (4 digits at most)?

I have an undergrad degree. Either I missed it or they didn't teach us, but how can I check (without using a computer) if a number, say 1033, is prime?
0
votes
2answers
53 views

Prove that for any integer $n$, if $b^2$ divides $n$, then $b$ divides $n$.

Prove that for any integer $n$, if $b^2$ divides $n$, then $b$ divides $n$. Trying to figure out this proof. The proof I'm looking at is written as $n$ = any integer, if $25|n \implies 5|n$. ...
2
votes
4answers
44 views

How do I prove that if $2\nmid n$ then $2|(n+1)$?

I'd like to prove a very simple fact, but it's stumping me: namely, that if $2 \nmid n$ then $2\mid(n+1)$. How would this usually be done?
1
vote
3answers
44 views

negative one times positive one is negative one

This is a question I was surprised that no one on this forum has asked(as far as my search went). I gave a proof that negative times negative = positive. But it relied on the assumption negative times ...
0
votes
0answers
46 views

PID and irreducibles

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}$. (c) Show that the only nonzero ideals of $R$ are ...
0
votes
0answers
16 views

Odd perfect numbers and $\sum_{\substack{D\mid 2n,D<\sqrt{2n}}}(D+\frac{2n}{D})$

It is known that if $m>1$ isn't a perfect square integer (isn't a square number) then the sum of divisor function can be written as $$\sigma(m)=\sum_{\substack{d\mid ...
0
votes
3answers
57 views

What is the difference between 10% and $\frac{1}{10}$

In a national competition , ech school had to choose 10% of students who participated in the competition . So my question is , why they didn't asked for $\frac{1}{10}$ of students who participated ? ...