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

learn more… | top users | synonyms

0
votes
1answer
28 views

Using Fermat's little theorem to find remainders. [duplicate]

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of 50^50 on division by 13, what is a and what is p in the formula? What is going on?? ...
0
votes
1answer
31 views

7-adic series expansion of square root of 2

Given the sequence $\{ a_n\}$ defined by the (positive and $a_n < 7^n$) solutions of the congruence $x^2 \equiv 2 \mod 7^n$ and $a_{n+1}\equiv a_n \mod 7^n$. e.g. the first one is $a_1 =3$ the ...
0
votes
0answers
6 views

Schemmel Totient Functions in Literature

I know how to prove that the Schemmel Totient functions are multiplicative, but I was wondering if someone could give me a reference to a place in the literature where such a proof is given.
1
vote
0answers
20 views

The logarithm of a product

Let $p$ be a prime number, $C\in \mathbb{N}$ and C is not a square. Then define $$F=\prod_{|z| \leq \sqrt{\frac{x}{2}} \atop |y|\leq \sqrt{\frac{x}{2}p}}{|z^2-Cy^2|}.$$ Note that we omit the term with ...
0
votes
2answers
29 views

Numbers in a list which are perfect squares and perfect cubes of numbers

How many numbers in the list $$1,2,3,...,2001$$ are perfect squares and perfect cubes of whole numbers? My progress: Well I do know $$1,4,9,16,25,36,...$$ are perfect squares and $$1,8,27,64,...$$ ...
0
votes
2answers
18 views

Perfect Square and Multiple question

The population of a village is a perfect square. Later, with an increase of 100, the population was 1 more than a perfect square. Now with an additional increase of 100, the population is a perfect ...
0
votes
1answer
14 views

Let a, b, and m be positive integers such that $(a,m) = (b,m) = 1$. Assume that $(ord_m(a), ord_m(b)) = 1$ Prove that $ord_m(ab) = ord_m(a)*ord_m(b) $

So I got $(ab)^{ord_m(a)*ord_m(b)} = 1 \bmod m$ so $ord_m(ab) \mid ord_m(a) * ord_m(b)$ I am stuck on how to proceed from here though
1
vote
3answers
34 views

prove that if $a$ is not a unit in $\mathbb Z$/m$\mathbb Z$ then $a$ is a zero divisor in $\mathbb Z$/m$\mathbb Z$?

Ho can I prove that if $a$ is not a unit in $\mathbb Z$/m$\mathbb Z$ then $a$ is a zero divisor in $\mathbb Z$/m$\mathbb Z$ ? I am stuck on this problem I would appreciate a lot your help thanks!!
0
votes
1answer
27 views

Digit reversal arithmetic

How many three-digit odd numbers become bigger when their digits are reversed? $$abc<cba$$ and $c$ is either 1,3,5,7,9. This is the furthest I managed to reach.
1
vote
2answers
53 views

Three-Digit numbers divisbile by 3

How many three digit numbers are divisible by 3 and have an additional property that the sum of of their digits is 4 times the middle digit? My approach: let the number be $abc$ so $$abc \equiv ...
3
votes
2answers
42 views

Conjecture on twin primes

Let $p$ and $p+2$ be both prime. I conjectured (with my ignorance) that $$p^{\frac{p+1}{2}}\equiv -1\mod{(p+2)}$$ except for $p=17,41,71,137, 191, 239....$ I verified this on Mathematica. So for ...
1
vote
0answers
25 views

Good introduction to number theory that develops and/or makes heavy use of commutative ring theory and lattice theory?

I'd like to learn some number theory, since it provides a lot of motivation for commutative ring theory and even some motivation for lattice theory (at least, that's the impression I'm under). ...
1
vote
1answer
26 views

Last two digit of number raised to exponents. [duplicate]

Find the last two digits of $3^{3^{2014}}$. Attempt: First I try to work with $3^{2014}$. So we can work on $\text{mod 10}$. Then, $$\begin{align}&3^1 \equiv 3\pmod{10}\\ &3^2 \equiv 9 ...
-3
votes
0answers
16 views

The integers mod sqrt{d} [on hold]

Show that $\mathbb{Z}[\sqrt{d}]$ has a unit which is neither $+1$ or $-1$. Conclude that $\mathbb{Z}[\sqrt{d}]$ has an infinite number of units.
0
votes
1answer
34 views

Using Fermat's Little theorem to prove that $12\mid n^2-1$ when $(n,6)=1$

I need help proving the first one via Fermat's little theorem. I need a hint, or a good starter!
0
votes
1answer
24 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
2
votes
2answers
70 views

How can you proof that the sum of three roots is irrational?

I would like to know how to proof that $\sqrt{2} + \sqrt{5} + \sqrt{7}$ is an irrational number. I know how to do the proof for a sum of to roots. Can I just define $\sqrt{2} + \sqrt{5} :=c$ and then ...
0
votes
0answers
13 views

Geographic representation of summations and floors

I am struggling to write this proof, and cannot figure out how to view this "geometrically:" Let $a$, $b\in\mathbb{N}$ be odd and relatively prime. Show that $$ ...
3
votes
0answers
31 views

Any rational as integer plus sum of $n$ reciprocals

Does there exist an integer $n$ with the following property? For any rational number $r$, there exist integers $a,b_1,\ldots,b_n$ such that $r=a+\sum_{i=1}^n\frac1{b_i}$.
-1
votes
0answers
42 views

Prove something is divisible by a prime [on hold]

Let $p$ be a prime. Prove that $\sum_{k=j}^{p-1} \frac{k!}{ j! (k-j)! }$ is divisible by $p$ $\forall$ $j \in \{0, ..., p-2\}$. Where this problem comes from: I am trying to prove that ...
-5
votes
0answers
37 views

Integer solutions to the equation (1/x)+(1/y)=1/N! [on hold]

I am trying to find the number of positive integral solutions $(x,y)$ to the equation: $$\frac 1x + \frac 1y = \frac 1{N!}$$ where $N$ is a positive integer.
0
votes
1answer
31 views

Help on a perfect square.

Consider a question, that xyxyxyxy cannot be a perfect square. How should i tackle this problem. All i use is it must be $0,1 ($mod $3,4)$ and then the math, are there any another beatiful ways ...
0
votes
3answers
26 views

Division with remainder (Pos/Neg & Neg/Pos)

I guess it is a elementary school question, however I could not be sure: What are the remainders when: $-8$ is divided by $3$ $8$ is divided by $-3$ According to: $0<r<n$ where $m=qn+r$ ...
3
votes
2answers
64 views

Is this proof rigorus?

Simple abstract algebra proof: Suppose that $a,b,c\in\mathbb{Z}$ with $a$ and $b$ relatively prime. If $a|bc$, then $a|c$. Proof 1 Since $a$ & $b$ relatively prime, $a|bc\Rightarrow a|c$ ...
1
vote
1answer
37 views

Sum of Digit squares

I like to create problems for myself, While playing with my calculator, I found the following result. Take any positive digit $a_0$, and let $a_n$ denote the sum of digit squares of $a_{n-1}$. Then ...
3
votes
1answer
65 views

An easy question on number theory

Let $p$ be an odd prime. Is there any positive integer $k>1$ such that $p^k-1$ be a power of 2, that is $p^k-1=2^{\alpha}$ for some $\alpha\in \mathbb{N}$?
1
vote
0answers
32 views

Math Problem 10 - 9 x 8 - 7 x 6 - 5 x 4 - 3 x 2 - 2 x 1 = 1 [on hold]

Put {}, [] and () in the expression 10 - 9 x 8 - 7 x 6 - 5 x 4 - 3 x 2 - 2 x 1 = 1 in order to be true.
2
votes
2answers
69 views

Last digits, numbers

Can anyone please help me? 1) Find the last digit of $7^{12345}$ 2) Find the last 2 digits of $3^{3^{2014}}$. Attempt: 1) By just setting the powers of $7$ we have $7^1 = 7$, $7^2=49$, $7^3=343$, ...
0
votes
1answer
27 views

Find $m$ such that $4 \nshortmid \phi(m)$

The above question is taken from Silvermans A Friendly Introduction to Number Theory, volume 3. Here's what I've got so far: I know that $$\phi(m) = \prod_{p|m} (p^{k-1})(p-1)$$ and I tried several ...
2
votes
2answers
26 views

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer if $n$ is odd then $n=2^{0}n$, but I dont know what to do when ...
0
votes
3answers
33 views

mutliplicative inverse

Let a = 216, M = 342865. Show that gcd(a,M) = 1. Hence find the mutliplicative inverse, a^-1 mod M. I don't really know what to seach up for this question, but if anyone can provide me a example of ...
1
vote
5answers
72 views

prove that $3$ does not divide $n^2+1$

How do I prove that $3$ does not divide $n^2+1$, for all $n\in\mathbb{Z}$, thought of in separate cases, but did not get, induction also was unable to ....
1
vote
0answers
20 views

Definition of Euler phi function

Why is $\phi(n)$ defined to be $$\phi(n) = |\{ 0 \le b < n \mid gcd(b,n) = 1 \}|$$ rather than $$\phi(n) = |\{ 0 < b < n \mid gcd(b,n) = 1 \}|$$ ? I realize it doesn't make a practical ...
1
vote
2answers
42 views

Solving for a random number less than 401, generated by multiplying two numbers less than 21.

So, at a math meeting tonight we decided to play a game where you try to solve for a random number between 1 and 400 generated by multiplying two numbers between 1 and 20 together. Basically the ...
1
vote
1answer
39 views

Fermat's little theorem and congruence classes

I don't understand how to use Fermat's little theorem to find remainders e.g if we are asked to find remainder of $50^{50}$ on division by $13$, what is a and what is $p$ in the formula? Also I ...
3
votes
5answers
108 views

$\sqrt[3]{2}$ is not the root of a quadratic with rational coefficients?

How can one show that $\sqrt[3]{2}$ is not a root of a quadratic with rational coefficients? It is clear that if $\sqrt[3]{2}$ is the root of such a quadratic, then it is also the root of a quadratic ...
1
vote
0answers
26 views

Almost perfect numbers

A positive integer $n$ is called almost perfect if the sum of its divisors smaller than $n$ is $n-1$. What are all almost perfect numbers $n$ such that some power $n^k$ is also almost perfect for at ...
4
votes
2answers
57 views

Squares modulo 2^n

How many squares are there modulo $2^n$? If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
2
votes
1answer
42 views

How do i prove this is a metric?

Define a metric $d$ on $\mathbb{Z}$ in the following manner: $d(x,y)=\min\{\frac{1}{n!} : n! \text{ divides } x-y \text{ where } n\in\mathbb{Z}^+ \}$ if $x\neq y$. $d(x,x)=0$ ...
2
votes
3answers
67 views

Prove that $7^{100}+3^{10}=8^{100}$ or $7^{100}+3^{10}<8^{100}$ [on hold]

Prove that $7^{100}+3^{10}=8^{100}$ or $7^{100}+3^{10}<8^{100}$ I tried using some theorems of divisibility, to show that one divides the other, and the other also divides the first, but could ...
1
vote
3answers
24 views

Number of quadractic residues $\mod p$ and $\mod n$.

Let $p$ be an odd prime. Then among the integers $\{1,2,3,\cdots,p-1\}$ exactly half are quadratic residues modulo $p$. I believe the above proposition. Let $n$ be an odd, square free ...
0
votes
0answers
36 views

Find all the primes $p$ for which $x^2\equiv13\pmod p$ has a solution.

I found that for $p=3$, we have $x^2\equiv2^2\equiv4\equiv13\pmod 3\equiv-9\equiv0\pmod 3$. But how do I find out all the primes such that this holds?
2
votes
0answers
25 views

Question on Fermat Numbers Factorization

Let $F_{n}=2^{2^n}+1$ be a Fermat number. A classic idea using orders and Fermat's Little Theorem shows that a prime divisor $p$ of $F_{n}$ must be of the form $p=k .2^{n+1}+1$. Furthermore, using the ...
1
vote
2answers
52 views

Interesting numbers

I was doing some math problems when I came across some interesting numbers such as: $1^3+5^3+3^3=153$ $4^3+0^3+7^3=407$ $3^3+7^3+0^3=370$ $3^3+7^3+1^3=371$ $8^4+2^4+0^4+8^4=8208$ My question is: ...
0
votes
1answer
54 views

Troubles with understanding the answer

I don't understand the proof. Where did they get the first line from? 21x11=1+5x46? Fermat's theorem in my view is a^46=_1mod47
0
votes
0answers
12 views

Relation between zeta function and number of zeros of a homogeneous polynomial

For $f$ a homogeneous polynomial (i.e., every monomial has the same degree), $K$ a field of $q$ elements, one defines the zeta function $Z_f(u)$ as $$ Z_f(u)=\exp(\sum_{s=1}^\infty N_su^s/s) $$ ...
1
vote
1answer
42 views

Why doesn't SAGE understand reduced expressions mod p in a finite field extension?

Suppose I have a finite field $\mathbb{F}_{13}$ and I would like to adjoin an element, $\zeta$, with order $3$, since $\mathbb{F}_{13}$ does not contain one. So consider $\mathbb{F}_{13}(\zeta)$. Then ...
2
votes
2answers
59 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
1
vote
3answers
40 views

system of linear congruences

How can I solve this system of linear congruences? $$2x\equiv 0\, \text{mod 3}\\ 3x\equiv 2\, \text{mod 5}\\ 5x\equiv 4\, \text{mod 7}$$ I don´t know where to start, I am having a lot of troubles, ...
2
votes
2answers
80 views

for what integers $x$ do there exist $x$ consecutives integers, the sum of whose squares is prime?

for what integers $x$ do there exist $x$ consecutives integers, the sum of whose squares is prime? I tried use $$1^2+2^2+...+n^2=\frac {n(n+1)(2n+1)}{6}$$